Energy Games in Multiweighted Automata

Warning

This publication doesn't include Faculty of Education. It includes Faculty of Informatics. Official publication website can be found on muni.cz.
Authors

FAHRENBERG Uli JUHL Line LARSEN Kim G. SRBA Jiří

Year of publication 2011
Type Article in Proceedings
Conference Proceedings of the 8th International Colloquium on Theoretical Aspects of Computing ({ICTAC}'11)
MU Faculty or unit

Faculty of Informatics

Citation
Doi http://dx.doi.org/10.1007/978-3-642-23283-1_9
Field Informatics
Keywords energy games; complexity; automata
Description 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 \eg~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.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.