Hostname: page-component-745bb68f8f-grxwn Total loading time: 0 Render date: 2025-02-07T03:44:24.907Z Has data issue: false hasContentIssue false
  • English
  • Français

The Determinacy of Context-Free Games

Published online by Cambridge University Press:  12 March 2014

Olivier Finkel
Olivier Finkel*
Affiliation:
Equipe de Logique Mathématique, Institut de Mathématiques de Jussieu - Paris Rive Gauche UMR 7586, CNRS et Université Paris Diderot Paris 7, Bâtiment Sophie Germain Case 7012, 75205 Paris Cedex 13, France, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by realtime 1-counter Büchi automata is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. We show also that the determinacy of Wadge games between two players in charge of ω-languages accepted by 1-counter Büchi automata is equivalent to the (effective) analytic Wadge determinacy. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton and a Büchi automaton such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(), L()); (2) There exists a model of ZFC in which the Wadge game W(L(), L()) is not determined. Moreover these are the only two possibilities, i.e. there are no models of ZFC in which Player 1 has a winning strategy in the Wadge game W(L(), L()).

Keywords

Automata and formal languageslogic in computer scienceGale-Stewart gamesWadge gamesdeterminacyeffective analytic determinacycontext-free games1-counter automatonmodels of set theoryindependence from the axiomatic system ZFC
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 78 , Issue 4 , December 2013 , pp. 1115 - 1134
Copyright
Copyright © Association for Symbolic Logic 2013

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Cachat, T., Higher order pushdown automata, the Caucal hierarchy of graphs and parity games, Automata, languages and programming, ICALP 2003 (Baeten, J. C. M., Lenstra, J. K., Parrow, J., and Woeginger, G. J., editors), Lecture Notes in Computer Science, vol. 2719, Springer, 2003, pp. 556–569.Google Scholar
[2] Carayol, A., Hague, M., Meyer, A., Ong, C.-H. L., and Serre, O., Winning regions of higher-order pushdown games, Logic in Computer Science, LICS 2008, IEEE Computer Society, 2008, pp. 193–204.Google Scholar
[3] Cohen, R. S. and Gold, A. Y., Theory of ω-languages. I. Characterizations of ω-context-free languages, Journal of Computer and System Sciences, vol. 15 (1977), no. 2, pp. 169–184.Google Scholar
[4] Cohen, R. S. and Gold, A. Y., ω-computations on Turing machines, Theoretical Computer Science, vol. 6 (1978), no. 1, pp. 1–23.CrossRefGoogle Scholar
[5] Engelfriet, J. and Hoogeboom, H. J., X-automata on ω-words, Theoretical Computer Science, vol. 110 (1993), no. 1, pp. 1–51.CrossRefGoogle Scholar
[6] Finkel, O., Borel hierarchy and omega context free languages, Theoretical Computer Science, vol. 290 (2003), no. 3, pp. 1385–1405.Google Scholar
[7] Finkel, O., Borel ranks and Wadge degrees of context free ω-languages, Mathematical Structures in Computer Science, vol. 16 (2006), no. 5, pp. 813–840.Google Scholar
[8] Finkel, O., The complexity of infinite computations in models of set theory, Logical Methods in Computer Science, vol. 5 (2009), no. 4:4, pp. 1–19.Google Scholar
[9] Finkel, O., Highly undecidable problems for infinite computations, Theoretical Informatics and Applications, vol. 43 (2009), no. 2, pp. 339–364.Google Scholar
[10] Finkel, O., The determinacy of context-free games, Theoretical Aspects of Computer Science, STACS 2012 (Dürr, Christoph and Wilke, Thomas, editors), LIPIcs, vol. 14, Leibniz International Proceedings in Informatics, 2012, pp. 555–566.Google Scholar
[11] Harrington, L., Analytic determinacy and 0# , this Journal, vol. 43 (1978), no. 4, pp. 685–693.Google Scholar
[12] Hopcroft, J. E., Motwani, R., and Ullman, J. D., Introduction to automata theory, languages, and computation, Addison-Wesley Series in Computer Science, Addison-Wesley, Reading, Mass., 1979.Google Scholar
[13] Jech, T., Set theory, third ed., Springer, 2002.Google Scholar
[14] Kechris, A. S., Classical descriptive set theory, vol. 156, Springer, 1995.Google Scholar
[15] Louveau, A. and Saint-Raymond, J., The strength of Borel Wadge determinacy, Cabal Seminar 81–85, Lecture Notes in Mathematics, vol. 1333, Springer, 1988, pp. 1–30.Google Scholar
[16] Martin, D. A., Measurable cardinals and analytic games, Fundamenta Mathematicae, vol. 66 (1969/1970), pp. 287–291.Google Scholar
[17] Moschovakis, Y. N., Descriptive set theory, North-Holland, Amsterdam, 1980.Google Scholar
[18] Odifreddi, P. G., Classical recursion theory. Vol. I, Studies in Logic and the Foundations of Mathematics, vol. 125, North-Holland, Amsterdam, 1989.Google Scholar
[19] Perrin, D. and Pin, J.-E., Infinite words, automata, semigroups, logic and games, Pure and Applied Mathematics, vol. 141, Elsevier, 2004.Google Scholar
[20] Sami, R. L., Analytic determinacy and 0#. A forcing-free proof of Harrington's theorem, Fundamenta Mathematicae, vol. 160 (1999), no. 2, pp. 153–159.Google Scholar
[21] Staiger, L., ω-languages, Handbook of formal languages, Vol. 3 (Rozenberg, G. and Salomaa, A., editors), Springer, 1997, pp. 339–387.Google Scholar
[22] Thomas, W., On the synthesis of strategies in infinite games, STACS 95, Lecture Notes in Computer Science, vol. 900, Springer, 1995, pp. 1–13.CrossRefGoogle Scholar
[23] Thomas, W., Church's problem and a tour through automata theory, Pillars of computer science, essays dedicated to Boris (Boaz) Trakhtenbrot on the occasion of his 85th birthday (Avron, Arnon, Dershowitz, Nachum, and Rabinovich, Alexander, editors), Lecture Notes in Computer Science, vol. 4800, Springer, 2008.Google Scholar
[24] Thomas, W. and Lescow, H., Logical specifications of infinite computations, A decade of concurrency (de Bakker, J. W., de Roever, Willem P., and Rozenberg, Grzegorz, editors), Lecture Notes in Computer Science, vol. 803, Springer, 1994, pp. 583–621.Google Scholar
[25] Wadge, W., Reducibility and determinateness in the Baire space, Ph.D. thesis, University of California, Berkeley, 1983.Google Scholar
[26] Walukiewicz, I., Pushdown processes: games and model-checking, Information and Computation, vol. 164 (2001), no. 2, pp. 234–263.CrossRefGoogle Scholar