The Determinacy of Context-Free Games
Copyright policy )The Determinacy of Context-Free Games
AbstractWe 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 automatonand a Büchi automatonsuch that: (1) There exists a model of ZFC in which Player 2 has a winning strategy in the Wadge gameW(L(),L()); (2) There exists a model of ZFC in which the Wadge gameW(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 gameW(L(),L()).
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], effective analytic determinacy, models of set theory, independence from the axiomatic system ZFC, context-free games, Computer Science - Computer Science and Game Theory, Gale-Stewart games, FOS: Mathematics, logic in computer science, Automata and formal languages, 1-counter automaton, independence from the axiomatic system ZFC., Mathematics - Logic, 004, Logic in Computer Science (cs.LO), Wadge games, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], determinacy, Logic (math.LO), Computer Science and Game Theory (cs.GT)
FOS: Computer and information sciences, Computer Science - Logic in Computer Science, [INFO.INFO-LO] Computer Science [cs]/Logic in Computer Science [cs.LO], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], effective analytic determinacy, models of set theory, independence from the axiomatic system ZFC, context-free games, Computer Science - Computer Science and Game Theory, Gale-Stewart games, FOS: Mathematics, logic in computer science, Automata and formal languages, 1-counter automaton, independence from the axiomatic system ZFC., Mathematics - Logic, 004, Logic in Computer Science (cs.LO), Wadge games, [INFO.INFO-GT] Computer Science [cs]/Computer Science and Game Theory [cs.GT], [MATH.MATH-LO] Mathematics [math]/Logic [math.LO], [INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC], determinacy, Logic (math.LO), Computer Science and Game Theory (cs.GT)
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).6 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!