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

DOI10.1051/ITA/2011113zbMath1232.68082arXiv1108.2864OpenAlexW2141635472MaRDI QIDQ3117545

Olivier Finkel

Publication date: 28 February 2012

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Abstract: We prove that some fairly basic questions on automata reading infinite words depend on the models of the axiomatic system ZFC. It is known that there are only three possibilities for the cardinality of the complement of an omega-language $L(A)$ accepted by a B"uchi 1-counter automaton $A$. We prove the following surprising result: there exists a 1-counter B"uchi automaton $A$ such that the cardinality of the complement $L(A)^-$ of the omega-language $L(A)$ is not determined by ZFC: (1). There is a model $V_1$ of ZFC in which $L(A)^-$ is countable. (2). There is a model $V_2$ of ZFC in which $L(A)^-$ has cardinal $2^{aleph_0}$. (3). There is a model $V_3$ of ZFC in which $L(A)^-$ has cardinal $aleph_1$ with $aleph_0<aleph_1<2^{aleph_0}$. We prove a very similar result for the complement of an infinitary rational relation accepted by a 2-tape B"uchi automaton $B$. As a corollary, this proves that the Continuum Hypothesis may be not satisfied for complements of 1-counter omega-languages and for complements of infinitary rational relations accepted by 2-tape B"uchi automata. We infer from the proof of the above results that basic decision problems about 1-counter omega-languages or infinitary rational relations are actually located at the third level of the analytical hierarchy. In particular, the problem to determine whether the complement of a 1-counter omega-language (respectively, infinitary rational relation) is countable is in $Sigma_3^1 setminus (Pi_2^1 cup Sigma_2^1)$. This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

Full work available at URL: https://arxiv.org/abs/1108.2864

zbMATH Keywords

decision problemsformal languagesinfinite wordsanalytical hierarchymodels of set theory1-counter automaton\(\omega \)-languages2-tape automatonaxiomatic system ZFCcardinality problemsindependence from ZFClargest thin effective coanalytic set

Mathematics Subject Classification ID

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)

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

Related Items (5)

Incompleteness Theorems, Large Cardinals, and Automata over Infinite Words ⋮ Incompleteness Theorems, Large Cardinals, and Automata Over Finite Words ⋮ Incompleteness Theorems, Large Cardinals, and Automata over Finite Words ⋮ Descriptive set theoretic methods in automata theory. Decidability and topological complexity ⋮ Wadge-Wagner hierarchies

This page was built for publication: Some problems in automata theory which depend on the models of set theory