The complexity of recursion theoretic games

DOI10.1090/S0002-9947-05-04074-2zbMath1079.03029MaRDI QIDQ5694972

No author found.

Publication date: 6 October 2005

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0002-9947-05-04074-2

zbMATH Keywords

undecidability; uniformity; analytical hierarchy; recursively enumerable sets; effective descriptive set theory; Borel games

Mathematics Subject Classification ID

91A05: 2-person games

03E15: Descriptive set theory

03D35: Undecidability and degrees of sets of sentences

91A46: Combinatorial games

03D25: Recursively (computably) enumerable sets and degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptive set theory
• Some undecidable determined games
• Recursively presented games and strategies
• Borel determinacy
• On the complexity of some two-person perfect-information games
• On some games which are relevant to the theory of recursively enumerable sets
• The elementary theory of recursively enumerable sets
• Automata, logics, and infinite games. A guide to current research
• Recursion in Kolmogorov's R-operator and the ordinal σ₃
• A Combinatorial Problem Which Is Complete in Polynomial Space
• On the Lattice of Recursively Enumerable Sets
• Solving Sequential Conditions by Finite-State Strategies
• Automata theory and its applications