Energy Games in Multiweighted Automata

U. Fahrenberg, L. Juhl, Kim Guldstrand Larsen, J. Srba

Publikation: Bidrag til tidsskriftKonferenceartikel i tidsskriftForskningpeer review

61 Citationer (Scopus)

Abstract

Energy games have recently attracted a lot of attention. These are games played on finite weighted automata and concern the existence of infinite runs subject to boundary constraints on the accumulated weight, allowing e.g only for behaviours where a resource is always available (nonnegative accumulated weight), yet does not exceed a given maximum capacity. We extend energy games to a multiweighted and parameterized setting, allowing us to model systems with multiple quantitative aspects. We present reductions between Petri nets and multiweighted automata and among different types of multiweighted automata and identify new complexity and (un)decidability results for both one- and two-player games. We also investigate the tractability of an extension of multiweighted energy games in the setting of timed automata.
OriginalsprogEngelsk
BogserieLecture Notes in Computer Science
Vol/bind6916
Sider (fra-til)95-115
Antal sider21
ISSN0302-9743
DOI
StatusUdgivet - 1 jan. 2011
Begivenhed8th International Colloquium on Theoretical Aspects of Computing - Johannesburg, Sydafrika
Varighed: 31 aug. 20112 sep. 2011
Konferencens nummer: 8

Konference

Konference8th International Colloquium on Theoretical Aspects of Computing
Nummer8
Land/OmrådeSydafrika
ByJohannesburg
Periode31/08/201102/09/2011

Bibliografisk note

Proceedings of the 8th International Colloquium on Theoretical Aspects of Computing - ICTAC 2011. (eds.) Cerone, Antonio & Pihlajasaari, Pekka.

Fingeraftryk

Dyk ned i forskningsemnerne om 'Energy Games in Multiweighted Automata'. Sammen danner de et unikt fingeraftryk.

Citationsformater