Energy Games in Multiweighted Automata

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

Research output: Contribution to journalConference article in JournalResearchpeer-review

50 Citations (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.
Original languageEnglish
Book seriesLecture Notes in Computer Science
Volume6916
Pages (from-to)95-115
Number of pages21
ISSN0302-9743
DOIs
Publication statusPublished - 1 Jan 2011
Event8th International Colloquium on Theoretical Aspects of Computing - Johannesburg, South Africa
Duration: 31 Aug 20112 Sep 2011
Conference number: 8

Conference

Conference8th International Colloquium on Theoretical Aspects of Computing
Number8
CountrySouth Africa
CityJohannesburg
Period31/08/201102/09/2011

Fingerprint

Computability and decidability
Finite automata
Petri nets
Automata
Game
Energy
Weighted Automata
Timed Automata
Tractability
Finite Automata
Decidability
Petri Nets
Exceed
Non-negative
Resources

Cite this

@inproceedings{d7344735a5344901b871ccc7fe5c9868,
title = "Energy Games in Multiweighted Automata",
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.",
author = "U. Fahrenberg and L. Juhl and Larsen, {Kim Guldstrand} and J. Srba",
note = "Proceedings of the 8th International Colloquium on Theoretical Aspects of Computing - ICTAC 2011. (eds.) Cerone, Antonio & Pihlajasaari, Pekka.",
year = "2011",
month = "1",
day = "1",
doi = "10.1007/978-3-642-23283-1_9",
language = "English",
volume = "6916",
pages = "95--115",
journal = "Lecture Notes in Computer Science",
issn = "0302-9743",
publisher = "Physica-Verlag",

}

Energy Games in Multiweighted Automata. / Fahrenberg, U.; Juhl, L.; Larsen, Kim Guldstrand; Srba, J.

In: Lecture Notes in Computer Science, Vol. 6916, 01.01.2011, p. 95-115.

Research output: Contribution to journalConference article in JournalResearchpeer-review

TY - GEN

T1 - Energy Games in Multiweighted Automata

AU - Fahrenberg, U.

AU - Juhl, L.

AU - Larsen, Kim Guldstrand

AU - Srba, J.

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

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?eid=2-s2.0-80052721475&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/record.url?scp=80052721475&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052721475&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23283-1_9

DO - 10.1007/978-3-642-23283-1_9

M3 - Conference article in Journal

AN - SCOPUS:80052721475

VL - 6916

SP - 95

EP - 115

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

SN - 0302-9743

ER -