Computer Science – Computer Science and Game Theory
Scientific paper
2011-12-06
Computer Science
Computer Science and Game Theory
To appear in the Proceedings of the 29 th International Symposium on Theoretical Aspects of Computer Science, STACS 2012
Scientific paper
10.4230/LIPIcs.STACS.2012.555
We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter B\"uchi 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\"uchi 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\"uchi automaton A and a B\"uchi 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)).
No associations
LandOfFree
The Determinacy of Context-Free Games does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Determinacy of Context-Free Games, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Determinacy of Context-Free Games will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-380410