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)
Abstract: We prove the following surprising result: there exist a 1-counter B"uchi automaton and a 2-tape B"uchi automaton such that the omega-language of the first and the infinitary rational relation of the second in one model of ZFC are pi_2^0-sets, while in a different model of ZFC both are analytic but non Borel sets. This shows that the topological complexity of an omega-language accepted by a 1-counter B"uchi automaton or of an infinitary rational relation accepted by a 2-tape B"uchi automaton is not determined by the axiomatic system ZFC. We show that a similar result holds for the class of languages of infinite pictures which are recognized by B"uchi tiling systems. We infer from the proof of the above results an improvement of the lower bound of some decision problems recently studied by the author.
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
