Collapsible Pushdown Parity Games
Authors: 
Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, Andrzej S. Murawski, C.-H. Luke Ong, Olivier SerreAuthors Info & Claims
Article No.: 16, Pages 1 - 51
Abstract
This article studies a large class of two-player perfect-information turn-based parity games on infinite graphs, namely, those generated by collapsible pushdown automata. The main motivation for studying these games comes from the connections from collapsible pushdown automata and higher-order recursion schemes, both models being equi-expressive for generating infinite trees. Our main result is to establish the decidability of such games and to provide an effective representation of the winning region as well as of a winning strategy. Thus, the results obtained here provide all necessary tools for an in-depth study of logical properties of trees generated by collapsible pushdown automata/recursion schemes.
References
[1]
Klaus Aehlig, Jolie de Miranda, and C.-H. Luke Ong. 2005. Safety is not a restriction at level 2 for string languages. In Proceedings of the 8th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS’05) (Lecture Notes in Computer Science), Vol. 3411. Springer-Verlag, 490–501.
[2]
André Arnold and Damian Niwiński. 2001. Rudiments of mu-Calculus(Studies in Logic and the Foundations of Mathematics, Vol. 146). Elsevier.
[3]
Ahmed Bouajjani and Antoine Meyer. 2004. Symbolic reachability analysis of higher-order context-free processes. In Proceedings of the 24th International Conference on Foundations of Software Technology and Theoretical Computer Science (FST&TCS’04) (Lecture Notes in Computer Science), Vol. 3328. Springer-Verlag, 135–147.
[4]
Christopher H. Broadbent. 2012. The limits of decidability for first order logic on CPDA graphs. In Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS’12) (LIPIcs), Vol. 14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 589–600.
[5]
Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, and Olivier Serre. 2012. A saturation method for collapsible pushdown systems. In Proceedings of the 39th International Colloquium on Automata, Languages, and Programming (ICALP’12) (Lecture Notes in Computer Science), Vol. 7392. Springer-Verlag, 165–176.
[6]
Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, and Olivier Serre. 2013. C-SHORe: A collapsible approach to higher-order verification. In Proceedings of the 18th ACM SIGPLAN International Conference on Functional Programming (ICFP’13). ACM, 13–24.
[7]
Christopher H. Broadbent, Arnaud Carayol, Matthew Hague, and Olivier Serre. 2020. Higher-Order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties. Retrieved from https://www.irif.fr/ serre//PublisMisc/BCOS20.pdf .
[8]
Christopher H. Broadbent, Arnaud Carayol, C.-H. Luke Ong, and Olivier Serre. 2010. Recursion schemes and logical reflexion. In Proceedings of the 25th IEEE Symposium on Logic in Computer Science (LiCS’10). IEEE Computer Society, 120–129.
[9]
Thierry Cachat. 2002. Uniform solution of parity games on prefix-recognizable graphs. In Proceedings of the 4th International Workshop on Verification of Infinite-State Systems, Infinity 2002 (Electronic Notes in Theoretical Computer Science), Vol. 68. Elsevier Science Publishers.
[10]
Thierry Cachat. 2003. Games on Pushdown Graphs and Extensions. Ph.D. Dissertation. RWTH Aachen.
[11]
Thierry Cachat. 2003. Higher order pushdown automata, the caucal hierarchy of graphs and parity games. In Proceedings of the 30th International Colloquium on Automata, Languages, and Programming (ICALP’03) (Lecture Notes in Computer Science), Vol. 2719. Springer-Verlag, 556–569.
[12]
Thierry Cachat and Igor Walukiewicz. 2007. The complexity of games on higher order pushdown automata. CoRR abs/0705.0262 (2007).
[13]
Arnaud Carayol. 2005. Regular sets of higher-order pushdown stacks. In Proceedings of the 30th Symposium, Mathematical Foundations of Computer Science (MFCS’05) (Lecture Notes in Computer Science), Vol. 3618. Springer-Verlag, 168–179.
[14]
Arnaud Carayol, Antoine Meyer, Matthew Hague, C.-H. Luke Ong, and Olivier Serre. 2008. Winning regions of higher-order pushdown games. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LiCS’08). IEEE Computer Society, 193–204.
[15]
Arnaud Carayol and Olivier Serre. 2012. Collapsible pushdown automata and labeled recursion schemes: Equivalence, safety and effective selection. In Proceedings of the 27th IEEE Symposium on Logic in Computer Science (LiCS’12). IEEE Computer Society, 165–174.
[16]
Arnaud Carayol and Michaela Slaats. 2008. Positional strategies for higher-order pushdown parity games. In Proceedings of the 33rd Symposium, Mathematical Foundations of Computer Science (MFCS’08) (Lecture Notes in Computer Science), Vol. 5162. Springer-Verlag, 217–228.
[17]
Didier Caucal. 2002. On infinite terms having a decidable monadic theory. In Proceedings of the 27th Symposium, Mathematical Foundations of Computer Science (MFCS’02) (Lecture Notes in Computer Science), Vol. 2420. Springer-Verlag, 165–176.
[18]
Bruno Courcelle. 1994. Monadic second-order definable graph transductions: A survey.Theoret. Comput. Sci. 126, 1 (1994), 53–75.
[19]
E. Allen Emerson and Charanjit S. Jutla. 1991. Tree automata, mu-calculus and determinacy (extended abstract). In Proceedings of the 32nd Symposium on Foundations of Computer Science (FoCS’91). IEEE Computer Society, 368–377.
[20]
Joost Engelfriet. 1991. Iterated stack automata and complexity classes. Inf. Computat. 95, 1 (1991), 21–75.
[21]
Yuri Gurevich and Leo Harrington. 1982. Trees, automata, and games. In Proceedings of the 14th ACM Symposium on the Theory of Computing (STOC’82). ACM, 60–65.
[22]
Matthew Hague. 2008. Global Model Checking of Higher-order Pushdown Systems. Ph.D. Dissertation. University of Oxford.
[23]
Matthew Hague, Andrzej S. Murawski, C.-H. Luke Ong, and Olivier Serre. 2008. Collapsible pushdown automata and recursion schemes. In Proceedings of the 23rd IEEE Symposium on Logic in Computer Science (LiCS’08). IEEE Computer Society, 452–461.
[24]
Matthew Hague, Andrzej S. Murawski, C.-H. Luke Ong, and Olivier Serre. 2017. Collapsible pushdown automata and recursion schemes. ACM Trans. Computat. Log. 18, 3 (2017), 25:1–25:42.
[25]
Matthew Hague and C.-H. Luke Ong. 2008. Symbolic backwards-reachability analysis for higher-order pushdown systems. Log. Meth. Comput. Sci. 4, 4 (2008).
[26]
Matthew Hague and C.-H. Luke Ong. 2011. A saturation method for the modal -calculus over pushdown systems. Inf. Computat. 209, 5 (2011), 799–821.
[27]
Alexander Kartzow. 2010. Collapsible pushdown graphs of level 2 are tree-automatic. In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS’10) (LIPIcs), Vol. 5. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 501–512.
[28]
Teodor Knapik, Damian Niwiński, Pawel Urzyczyn, and Igor Walukiewicz. 2005. Unsafe grammars and panic automata. In Proceedings of the 32nd International Colloquium on Automata, Languages, and Programming (ICALP’05) (Lecture Notes in Computer Science), Vol. 3580. Springer-Verlag, 1450–1461.
[29]
Donald A. Martin. 1975. Borel determinacy. Ann. Math. 102, 2 (1975), 363–371.
[30]
David. E. Muller and Paul. E. Schupp. 1985. The theory of ends, pushdown automata, and second-order logic. Theoret. Comput. Sci. 37 (1985), 51–75.
[31]
Michael O. Rabin. 1969. Decidability of second-order theories and automata on infinite trees. Trans. Amer. Math. Soc. 141 (1969), 1–35.
[32]
Olivier Serre. 2003. Note on winning positions on pushdown games with -regular winning conditions. Inf. Proc. Lett. 85 (2003), 285–291.
[33]
Olivier Serre. 2004. Contribution à l’étude des jeux sur des graphes de processus à pile. Ph.D. Dissertation. Université Paris 7.
[34]
Colin Stirling. 2009. Dependency tree automata. In Proceedings of the 12th International Conference on Foundations of Software Science and Computational Structures (FoSSaCS’09) (Lecture Notes in Computer Science), Vol. 5504. Springer-Verlag, 92–106.
[35]
Wolfgang Thomas. 1997. Languages, automata, and logic. In Handbook of Formal Language Theory, G. Rozenberg and A. Salomaa (Eds.). Vol. III. Springer-Verlag, 389–455.
[36]
Moshe Y. Vardi. 1998. Reasoning about the past with two-way automata. In Proceedings of the 25th International Colloquium on Automata, Languages, and Programming (ICALP’98) (Lecture Notes in Computer Science), Vol. 1443. Springer-Verlag, 628–641.
[37]
Igor Walukiewicz. 1996. Pushdown processes: Games and model checking. In Proceeding of the 8th International Conference on Computer-aided Verification (CAV’96) (Lecture Notes in Computer Science), Vol. 1102. Springer-Verlag, 62–74.
[38]
Igor Walukiewicz. 2001. Pushdown processes: Games and model-checking. Inf. Computat. 157 (2001), 234–263.
[39]
Igor Walukiewicz. 2004. A landscape with games in the background. In Proceedings of the 19th IEEE Symposium on Logic in Computer Science (LiCS’04). Computer Society Press, 356–366.
[40]
Thomas Wilke. 2001. Alternating tree automata, parity games and modal -calculus. Bull. Belgian Math. Soc. 8, 2 (2001), 359–391.
[41]
Stefan Wöhrle and Wolfgang Thomas. 2007. Model checking synchronized products of infinite transition systems. Log. Meth. Comput. Sci. 3, 4 (2007).
Index Terms
- Collapsible Pushdown Parity Games
Recommendations
Higher-order Recursion Schemes and Collapsible Pushdown Automata: Logical Properties
This article studies the logical properties of a very general class of infinite ranked trees, namely, those generated by higher-order recursion schemes. We consider, for both monadic second-order logic and modal -calculus, three main problems: model-...
Collapsible Pushdown Automata and Recursion Schemes
We consider recursion schemes (not assumed to be homogeneously typed, and hence not necessarily safe) and use them as generators of (possibly infinite) ranked trees. A recursion scheme is essentially a finite typed deterministic term rewriting system ...
Visibly pushdown games
FSTTCS'04: Proceedings of the 24th international conference on Foundations of Software Technology and Theoretical Computer ScienceThe class of visibly pushdown languages has been recently defined as a subclass of context-free languages with desirable closure properties and tractable decision problems. We study visibly pushdown games, which are games played on visibly pushdown ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2021
186 pages
Copyright © 2021 Association for Computing Machinery.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 28 June 2021
Accepted: 01 March 2021
Received: 01 October 2020
Published in TOCL Volume 22, Issue 3
Check for updates
Author Tags
Qualifiers
- Research-article
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 82Total Downloads
- Downloads (Last 12 months)4
- Downloads (Last 6 weeks)1
Reflects downloads up to 13 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format