The complexity of recursion theoretic games

DOI10.1090/S0002-9947-05-04074-2MaRDI QIDQ5694972zbMATH OpenOpenAlexFDO

Authors

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

analytical hierarchyBorel gameseffective descriptive set theoryrecursively enumerable setsundecidabilityuniformity

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Undecidability and degrees of sets of sentences (03D35) Descriptive set theory (03E15) 2-person games (91A05) Combinatorial games (91A46)

Recommendations

• scientific article; zbMATH DE number 2067969
• On the complexity of searching game trees and other recursion trees
• On the complexity of counter reachability games
• On the Complexity of Counter Reachability Games
• On the complexity of problems on simple games
• Expository notes on computability and complexity in (arithmetical) games
• scientific article; zbMATH DE number 1054025
• Mathematical Foundations of Computer Science 2005
• Finite complexity and the folk theorem in repeated games
• Repeated games, finite automata, and complexity

Cites work

• A Combinatorial Problem Which Is Complete in Polynomial Space
• Automata theory and its applications
• Automata, logics, and infinite games. A guide to current research
• Borel determinacy
• Descriptive set theory
• scientific article; zbMATH DE number 3835792 (Why is no real title available?)
• scientific article; zbMATH DE number 3128730 (Why is no real title available?)
• scientific article; zbMATH DE number 3143608 (Why is no real title available?)
• scientific article; zbMATH DE number 3861137 (Why is no real title available?)
• scientific article; zbMATH DE number 3908418 (Why is no real title available?)
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3761989 (Why is no real title available?)
• scientific article; zbMATH DE number 3628936 (Why is no real title available?)
• scientific article; zbMATH DE number 1209711 (Why is no real title available?)
• scientific article; zbMATH DE number 1232130 (Why is no real title available?)
• scientific article; zbMATH DE number 610968 (Why is no real title available?)
• scientific article; zbMATH DE number 3215740 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• On some games which are relevant to the theory of recursively enumerable sets
• On the complexity of some two-person perfect-information games
• On the Lattice of Recursively Enumerable Sets
• Recursion in Kolmogorov's R-operator and the ordinal σ₃
• Recursively presented games and strategies
• Solving Sequential Conditions by Finite-State Strategies
• Some undecidable determined games
• The elementary theory of recursively enumerable sets

Cited in

(15)

• Recursively presented games and strategies
• Nondeterminacy and recursion via stacks and games
• Expository notes on computability and complexity in (arithmetical) games
• The recursive core for non-superadditive games
• ON THE COMPLEXITY OF COMPUTING VALUES OF RESTRICTED GAMES
• Recursive algorithm for parity games requires exponential time
• scientific article; zbMATH DE number 7498449 (Why is no real title available?)
• Complexity of Winning Strategies for Δ 0 2 Games
• scientific article; zbMATH DE number 2067969 (Why is no real title available?)
• Recursive comparison tests for dicot and dead-ending games under misère play
• Complexity of Unordered CNF Games
• On the Complexity of Counter Reachability Games
• Effective strategies for enumeration games
• Compression of enumerations and gain
• A note on degrees of presentation of games as relational structures

This page was built for publication: The complexity of recursion theoretic games

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5694972)