Some problems in automata theory which depend on the models of set theory
Publication:3117545
DOI10.1051/ita/2011113zbMath1232.68082arXiv1108.2864OpenAlexW2141635472MaRDI QIDQ3117545
Publication date: 28 February 2012
Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1108.2864
decision problemsformal languagesinfinite wordsanalytical hierarchymodels of set theory1-counter automaton\(\omega \)-languages2-tape automatonaxiomatic system ZFCcardinality problemsindependence from ZFClargest thin effective coanalytic set
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Turing machines and related notions (03D10)
Related Items (4)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Relations rationnelles infinitaires
- \(\omega\)-computations on Turing machines
- The monadic theory of ω2
- The Complexity of Infinite Computations In Models of Set Theory
- Borel ranks and Wadge degrees of context free $\omega$-languages
- Finite state automata and monadic definability of singular cardinals
- Highly Undecidable Problems For Infinite Computations
- Nondeterministic Ω-Computations and the Analytical Hierarchy
- The Theory of Countable Analytical Sets
- The Mathematical Import of Zermelo's Well-Ordering Theorem
- First-order and counting theories ofω-automatic structures
- On the Accepting Power of 2-Tape Büchi Automata
- Decision problems forω-automata
This page was built for publication: Some problems in automata theory which depend on the models of set theory
