The Complexity of Infinite Computations In Models of Set Theory
From MaRDI portal
Publication:3401139
DOI10.2168/LMCS-5(4:4)2009zbMath1191.03034arXiv0910.1268MaRDI QIDQ3401139
Publication date: 28 January 2010
Published in: Logical Methods in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/0910.1268
Borel setstopological complexityinfinite wordsmodels of set theory1-counter automatontwo-dimensional wordstiling systemsCantor topology\(\omega \)-languages2-tape automatonindependence from ZFCeffective coanalytic set
Descriptive set theory (03E15) Automata and formal grammars in connection with logical questions (03D05) Consistency and independence results (03E35)
Related Items (9)
Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words ⋮ Infinite games specified by 2-tape automata ⋮ Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words ⋮ Incompleteness Theorems, Large Cardinals, and Automata over Finite Words ⋮ Polishness of some topologies related to word or tree automata ⋮ Locally finite ω-languages and effective analytic sets have the same topological complexity ⋮ Wadge-Wagner hierarchies ⋮ Some problems in automata theory which depend on the models of set theory ⋮ On the Expressive Power of Non-deterministic and Unambiguous Petri Nets over Infinite Words
This page was built for publication: The Complexity of Infinite Computations In Models of Set Theory
