Some problems in automata theory which depend on the models of set theory

DOI10.1051/ita/2011113zbMath1232.68082arXiv1108.2864MaRDI QIDQ3117545

Olivier Finkel

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

zbMATH Keywords

decision problems; formal languages; infinite words; analytical hierarchy; models of set theory; 1-counter automaton; \(\omega \)-languages; 2-tape automaton; axiomatic system ZFC; cardinality problems; independence from ZFC; largest thin effective coanalytic set

Mathematics Subject Classification ID

68Q45: Formal languages and automata

03D05: Automata and formal grammars in connection with logical questions

68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)

03D10: Turing machines and related notions

Related Items

Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words, Wadge-Wagner hierarchies, Incompleteness Theorems, Large Cardinals, and Automata over Finite Words, Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words

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 ω₂
• 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