Positional ω-regular languages
Article No.: 21, Pages 1 - 14
Abstract
In the context of two-player games over graphs, a language L is called positional if, in all games using L as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on the history of the play. In this work, we describe the class of parity automata recognising positional languages, providing a characterisation of positionality for ω-regular languages. As corollaries, we establish decidability of positionality in polynomial time, finite-to-infinite and 1-to-2-players lifts, and show the closure under union of prefix-independent positional objectives, answering a conjecture by Kopczyński in the ω-regular case.
References
[1]
Bader Abu Radi and Orna Kupferman. Minimization and canonization of GFG transition-based automata. Log. Methods Comput. Sci., 18(3), 2022.
[2]
André Arnold. A syntactic congruence for rational omega-language. Theor. Comput. Sci., 39:333--335, 1985.
[3]
Alessandro Bianco, Marco Faella, Fabio Mogavero, and Aniello Murano. Exploring the boundary of half-positionality. Ann. Math. Artif. Intell., 62(1-2):55--77, 2011.
[4]
Roderick Bloem, Krishnendu Chatterjee, and Barbara Jobstmann. Graph games and reactive synthesis. In Edmund M. Clarke, Thomas A. Henzinger, Helmut Veith, and Roderick Bloem, editors, Handbook of Model Checking, pages 921--962. Springer International Publishing, 2018.
[5]
León Bohn and Christof Löding. Constructing deterministic parity automata from positive and negative examples. CoRR, abs/2302.11043, 2023.
[6]
Udi Boker and Karoliina Lehtinen. When a little nondeterminism goes a long way: An introduction to history-determinism. ACM SIGLOG News, 10(1):24--51, 2023.
[7]
Patricia Bouyer, Antonio Casares, Mickael Randour, and Pierre Vandenhove. Half-positional objectives recognized by deterministic Büchi automata. In CONCUR, volume 243, pages 20:1--20:18, 2022.
[8]
Patricia Bouyer, Ulrich Fahrenberg, Kim Guldstrand Larsen, Nicolas Markey, and Jiri Srba. Infinite runs in weighted timed automata with energy constraints. In FORMATS, volume 5215 of Lecture Notes in Computer Science, pages 33--47, 2008.
[9]
Patricia Bouyer, Nathanaël Fijalkow, Mickael Randour, and Pierre Vandenhove. How to play optimally for regular objectives? In ICALP, volume 261 of LIPIcs, pages 118:1--118:18, 2023.
[10]
Patricia Bouyer, Mickael Randour, and Pierre Vandenhove. Characterizing omega-regularity through finite-memory determinacy of games on infinite graphs. TheoretiCS, 2, 2023.
[11]
Patricia Bouyer, Stéphane Le Roux, Youssouf Oualhadj, Mickael Randour, and Pierre Vandenhove. Games where you can play optimally with arena-independent finite memory. In CONCUR, volume 171, pages 24:1--24:22, 2020.
[12]
J. Richard Büchi and Lawrence H. Landweber. Solving sequential conditions by finite-state strategies. Transactions of the American Mathematical Society, 138:295--311, 1969. URL: http://www.jstor.org/stable/1994916.
[13]
J. Richard Büchi. On a decision method in restricted second order arithmetic. Proc. Internat. Congr. on Logic, Methodology and Philosophy of Science, pages 1--11, 1962.
[14]
Olivier Carton and Ramón Maceiras. Computing the Rabin index of a parity automaton. RAIRO, pages 495--506, 1999.
[15]
Antonio Casares. On the minimisation of transition-based Rabin automata and the chromatic memory requirements of Muller conditions. In CSL, volume 216, pages 12:1--12:17, 2022. 2.
[16]
Antonio Casares. Structural properties of automata over infinite words and memory for games (Propriétés structurelles des automates sur les mots infinis et mémoire pour les jeux). Phd thesis, Université de Bordeaux, France, 2023. URL: https://theses.hal.science/tel-04314678.
[17]
Antonio Casares, Thomas Colcombet, Nathanaël Fijalkow, and Karoliina Lehtinen. From Muller to Parity and Rabin Automata: Optimal Transformations Preserving (History) Determinism. TheoretiCS, Volume 3, April 2024.
[18]
Antonio Casares, Thomas Colcombet, and Karoliina Lehtinen. On the size of good-for-games Rabin automata and its link with the memory in Muller games. In ICALP, volume 229, pages 117:1--117:20, 2022.
[19]
Antonio Casares and Pierre Ohlmann. Characterising memory in infinite games. In ICALP, volume 261 of LIPIcs, pages 122:1--122:18, 2023.
[20]
Antonio Casares and Pierre Ohlmann. Positional ω-regular languages. CoRR, abs/2401.15384, 2024. arXiv:2401.15384
[21]
Edmund M. Clarke, I. A. Draghicescu, and Robert P. Kurshan. A unified approch for showing language inclusion and equivalence between various types ofomega-automata. Inf. Process. Lett., 46(6):301--308, 1993.
[22]
Thomas Colcombet, Nathanaël Fijalkow, Pawel Gawrychowski, and Pierre Ohlmann. The theory of universal graphs for infinite duration games. Log. Methods Comput. Sci., 18(3), 2022.
[23]
Thomas Colcombet, Nathanaël Fijalkow, and Florian Horn. Playing safe. In FSTTCS, volume 29, pages 379--390, 2014.
[24]
Thomas Colcombet and Damian Niwiński. On the positional determinacy of edge-labeled games. Theor. Comput. Sci., 352(1-3):190--196, 2006.
[25]
Stefan Dziembowski, Marcin Jurdziński, and Igor Walukiewicz. How much memory is needed to win infinite games? In LICS, pages 99--110, 1997.
[26]
Rüdiger Ehlers and Sven Schewe. Natural colors of infinite words. In FSTTCS, volume 250, pages 36:1--36:17, 2022.
[27]
E. Allen Emerson and Charanjit S. Jutla. Tree automata, mu-calculus and determinacy (extended abstract). In FOCS, pages 368--377, 1991.
[28]
Hugo Gimbert and Wieslaw Zielonka. Games where you can play optimally without any memory. In CONCUR, volume 3653, pages 428--442, 2005.
[29]
Marcin Jurdzinski. Small progress measures for solving parity games. In STACS, volume 1770 of Lecture Notes in Computer Science, pages 290--301, 2000.
[30]
Nils Klarlund. Progress measures, immediate determinacy, and a subset construction for tree automata. Annals of Pure and Applied Logic, 69(2):243--268, 1994.
[31]
Eryk Kopczyński. Omega-regular half-positional winning conditions. In CSL, volume 4646 of Lecture Notes in Computer Science, pages 41--53, 2007.
[32]
Eryk Kopczyński. Half-positional Determinacy of Infinite Games. PhD thesis, University of Warsaw, 2008.
[33]
Alexander Kozachinskiy. One-to-two-player lifting for mildly growing memory. In STACS, volume 219 of LIPIcs, pages 43:1--43:21, 2022.
[34]
Alexander Kozachinskiy. Energy games over totally ordered groups. In CSL, volume 288, pages 34:1--34:12, 2024.
[35]
Denis Kuperberg and Michal Skrzypczak. On determinisation of good-for-games automata. In ICALP, pages 299--310, 2015.
[36]
Orna Kupferman. Using the past for resolving the future. Frontiers Comput. Sci., 4, 2022.
[37]
Oded Maler and Ludwig Staiger. On syntactic congruences for ω-languages. Theoretical Computer Science, 183(1):93--112, 1997. Formal Language Theory.
[38]
Robert McNaughton. Testing and generating infinite sequences by a finite automaton. Information and control, 9(5):521--530, 1966.
[39]
Andrzej W. Mostowski. Regular expressions for infinite trees and a standard form of automata. In SCT, pages 157--168, 1984.
[40]
Pierre Ohlmann. Monotonic graphs for parity and mean-payoff games. (Graphes monotones pour jeux de parité et à paiement moyen). PhD thesis, Université Paris Cité, France, 2021. URL: https://tel.archives-ouvertes.fr/tel-03771185.
[41]
Pierre Ohlmann. Characterizing positionality in games of infinite duration over infinite graphs. TheoretiCS, 2, 2023.
[42]
Pierre Ohlmann and Michal Skrzypczak. Positionality in Σ02 and a completeness result. In STACS, volume 289, pages 54:1--54:18, 2024.
[43]
Bertrand Le Saëc. Saturating right congruences. RAIRO, 24:545--559, 1990.
[44]
Michal Skrzypczak. Topological extension of parity automata. Information and Computation, 228-229:16--27, 2013.
[45]
Wolfgang Thomas. On the synthesis of strategies in infinite games. In STACS, pages 1--13, 1995.
[46]
Pierre Vandenhove. Strategy complexity of zero-sum games on graphs. (Complexité des stratégies des jeux sur graphes à somme nulle). PhD thesis, University of Mons, Belgium, 2023. URL: https://tel.archives-ouvertes.fr/tel-04095220.
[47]
Igor Walukiewicz. Pushdown processes: Games and model checking. In CAV, volume 1102 of Lecture Notes in Computer Science, pages 62--74, 1996.
[48]
Wieslaw Zielonka. An invitation to play. In MFCS, volume 3618, pages 58--70, 2005.
Index Terms
- Positional ω-regular languages
Recommendations
Omega-regular half-positional winning conditions
CSL'07/EACSL'07: Proceedings of the 21st international conference, and Proceedings of the 16th annuall conference on Computer Science LogicWe study infinite games where one of the players always has a positional (memory-less) winning strategy, while the other player may use a history-dependent strategy. We investigate winning conditions which guarantee such a property for all arenas, or ...
Characterizing Positionality in Games of Infinite Duration over Infinite Graphs
LICS '22: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer ScienceWe study turn-based quantitative games of infinite duration opposing two antagonistic players and played over graphs. This model is widely accepted as providing the adequate framework for formalizing the synthesis question for reactive systems. This ...
Rabin-Mostowski Index Problem: A Step beyond Deterministic Automata
LICS '13: Proceedings of the 2013 28th Annual ACM/IEEE Symposium on Logic in Computer ScienceFor a given regular language of infinite trees, one can ask about the minimal number of priorities needed to recognise this language with a non-deterministic or alternating parity automaton. These questions are known as, respectively, the non-...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2024
988 pages
ISBN:9798400706608
DOI:10.1145/3661814
- Conference Chair:
- Pawel Sobocinski,
- Program Chairs:
- Ugo Dal Lago,
- Javier Esparza
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
- SIGLOG: ACM Special Interest Group on Logic and Computation
- IEEE Computer Society
In-Cooperation
- EACSL
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 08 July 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Narodowy Centrum Nauki
Conference
LICS '24
Sponsor:
LICS '24: 39th Annual ACM/IEEE Symposium on Logic in Computer Science
July 8 - 11, 2024
Tallinn, Estonia
Acceptance Rates
LICS '24 Paper Acceptance Rate 72 of 236 submissions, 31%;
Overall Acceptance Rate 215 of 622 submissions, 35%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 91Total Downloads
- Downloads (Last 12 months)91
- Downloads (Last 6 weeks)27
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in