Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2012.555
URN: urn:nbn:de:0030-drops-33897
URL: https://drops.dagstuhl.de/opus/volltexte/2012/3389/
Finkel, Olivier
The Determinacy of Context-Free Games
| pdf-format: |
|
Abstract
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 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 omega-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 A and a Büchi automaton B such that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge game W(L(A), L(B)); (2) There exists a model of ZFC in which the Wadge game W(L(A), L(B)) 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(A), L(B)).
BibTeX - Entry
@InProceedings{finkel:LIPIcs:2012:3389,
author = {Olivier Finkel},
title = {{The Determinacy of Context-Free Games}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {555--566},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-35-4},
ISSN = {1868-8969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3389},
URN = {urn:nbn:de:0030-drops-33897},
doi = {10.4230/LIPIcs.STACS.2012.555},
annote = {Keywords: Automata and formal languages, logic in computer science, Gale-Stewart games, Wadge games, determinacy, context-free games}
}
| Keywords: | Automata and formal languages, logic in computer science, Gale-Stewart games, Wadge games, determinacy, context-free games | |
| Seminar: | 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012) | |
| Issue date: | 2012 | |
| Date of publication: | 24.02.2012 |
