Finkel, Olivier
The Determinacy of ContextFree Games
Abstract
We prove that the determinacy of GaleStewart games whose winning sets are accepted by realtime 1counter Büchi automata is equivalent to the determinacy of (effective) analytic GaleStewart 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 omegalanguages accepted by 1counter 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 1counter 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 ContextFree Games}},
booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)},
pages = {555566},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897354},
ISSN = {18688969},
year = {2012},
volume = {14},
editor = {Christoph D{\"u}rr and Thomas Wilke},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2012/3389},
URN = {urn:nbn:de:0030drops33897},
doi = {http://dx.doi.org/10.4230/LIPIcs.STACS.2012.555},
annote = {Keywords: Automata and formal languages, logic in computer science, GaleStewart games, Wadge games, determinacy, contextfree games}
}
2012
Keywords: 

Automata and formal languages, logic in computer science, GaleStewart games, Wadge games, determinacy, contextfree games 
Seminar: 

29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)

Related Scholarly Article: 


Issue date: 

2012 
Date of publication: 

2012 