Parity and Streett Games with Costs

Nathanaël Fijalkow; Martin Zimmermann

doi:10.2168/LMCS-10(2:14)2014

Nathanaël Fijalkow ; Martin Zimmermann - Parity and Streett Games with Costs

lmcs:794 - Logical Methods in Computer Science, June 26, 2014, Volume 10, Issue 2 - https://doi.org/10.2168/LMCS-10(2:14)2014

Parity and Streett Games with CostsArticle

Authors: Nathanaël Fijalkow ; Martin Zimmermann

We consider two-player games played on finite graphs equipped with costs on edges and introduce two winning conditions, cost-parity and cost-Streett, which require bounds on the cost between requests and their responses. Both conditions generalize the corresponding classical omega-regular conditions and the corresponding finitary conditions. For parity games with costs we show that the first player has positional winning strategies and that determining the winner lies in NP and coNP. For Streett games with costs we show that the first player has finite-state winning strategies and that determining the winner is EXPTIME-complete. The second player might need infinite memory in both games. Both types of games with costs can be solved by solving linearly many instances of their classical variants.

https://doi.org/10.2168/LMCS-10(2:14)2014

Source: arXiv.org:1207.0663

Volume: Volume 10, Issue 2

Published on: June 26, 2014

Imported on: June 5, 2013

Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Computer Science - Computer Science and Game Theory

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

Expressive Power of Tree Logics; Funder: European Commission; Code: 239850
Games and Automata for Logic Extensions; Funder: European Commission; Code: 259454

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Bibliographic References

18 Documents citing this article

Ashwani Anand;Nathanaël Fijalkow;Aliénor Goubault-Larrecq;Jérôme Leroux;Pierre Ohlmann, 2021, New Algorithms for Combinations of Objectives using Separating Automata, arXiv (Cornell University), 346, pp. 227-240, 10.4204/eptcs.346.15.

Alexander Weinert, 2020, Quantitative reductions and vertex-ranked infinite games, arXiv (Cornell University), 278, pp. 104596, 10.1016/j.ic.2020.104596, https://arxiv.org/abs/1809.03887.

Aniello Murano;Sasha Rubin;Martin Zimmermann, 2020, Optimal Strategies in Weighted Limit Games, arXiv (Cornell University), 326, pp. 114-130, 10.4204/eptcs.326.8.

Laura Bozzelli;Aniello Murano;Giuseppe Perelli;Loredana Sorrentino, 2020, Hierarchical cost-parity games, Leibniz-Zentrum für Informatik (Schloss Dagstuhl), 847, pp. 147-174, 10.1016/j.tcs.2020.10.002, https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2017.6.

Corina Cîrstea, 2019, Resource-Aware Automata and Games for Optimal Synthesis, arXiv (Cornell University), 305, pp. 50-65, 10.4204/eptcs.305.4.

Daniel Neider;Alexander Weinert;Martin Zimmermann, 2019, Synthesizing optimally resilient controllers, Acta Informatica, 57, 1-2, pp. 195-221, 10.1007/s00236-019-00345-7, https://doi.org/10.1007/s00236-019-00345-7.

Valentin Goranko;Antti Kuusisto;Raine Rönnholm, 2019, Alternating-time temporal logic ATL with finitely bounded semantics, Theoretical Computer Science, 797, pp. 129-155, 10.1016/j.tcs.2019.05.029, https://doi.org/10.1016/j.tcs.2019.05.029.

Alexander Weinert, 2018, Quantitative Reductions and Vertex-Ranked Infinite Games, arXiv (Cornell University), 277, pp. 1-15, 10.4204/eptcs.277.1.

Massimo Benerecetti;Daniele Dell'Erba;Fabio Mogavero, 2018, A delayed promotion policy for parity games, Information and Computation, 262, pp. 221-240, 10.1016/j.ic.2018.09.005, https://doi.org/10.1016/j.ic.2018.09.005.

Massimo Benerecetti;Daniele Dell’Erba;Fabio Mogavero, 2018, Solving parity games via priority promotion, Oxford University Research Archive (ORA) (University of Oxford), 52, 2, pp. 193-226, 10.1007/s10703-018-0315-1, https://ora.ox.ac.uk/objects/uuid:db0d91fd-11a4-47b4-8d83-c8dc3a23f654.

Stéphane Le Roux;Arno Pauly, 2018, Extending finite-memory determinacy to multi-player games, Cronfa (Swansea University), 261, pp. 676-694, 10.1016/j.ic.2018.02.024, https://cronfa.swan.ac.uk/Record/cronfa36014/Download/0036014-08122017143113.pdf.

Martin Zimmermann, 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), Games with costs and delays, 68, pp. 1-12, 2017, Reykjavik, Iceland, 10.1109/lics.2017.8005125.

Martin Zimmermann, 2016, Parameterized linear temporal logics meet costs: still not costlier than LTL, arXiv (Cornell University), 55, 2, pp. 129-152, 10.1007/s00236-016-0279-9, http://arxiv.org/abs/1509.07206.

Stéphane Le Roux;Arno Pauly, 2016, Extending Finite Memory Determinacy to Multiplayer Games, arXiv (Cornell University), 218, pp. 27-40, 10.4204/eptcs.218.3.

Véronique Bruyère;Quentin Hautem;Mickael Randour, 2016, Window Parity Games: An Alternative Approach Toward Parity Games with Time Bounds, arXiv (Cornell University), 226, pp. 135-148, 10.4204/eptcs.226.10.

Martin Zimmermann, 2015, Parameterized Linear Temporal Logics Meet Costs: Still not Costlier than LTL, arXiv (Cornell University), 193, pp. 144-157, 10.4204/eptcs.193.11.

Martin Zimmermann, CiteSeer X (The Pennsylvania State University), Delay Games with WMSO$$+$$U Winning Conditions, pp. 412-425, 2015, 10.1007/978-3-319-20297-6_26, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.721.9497.

Mikołaj Bojańczyk, 2014, Automata column, ACM SIGLOG News, 1, 1, pp. 4, 10.1145/2657460.2657462, https://doi.org/10.1145/2657460.2657462.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 1870 times.

This article's PDF has been downloaded 375 times.