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

Finkel, Olivier 

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 383-397

Résumé

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\left(𝒜\right)$ accepted by a Büchi 1-counter automaton $𝒜$. We prove the following surprising result: there exists a 1-counter Büchi automaton $𝒜$ such that the cardinality of the complement $L{\left(𝒜\right)}^{-}$ of the $\omega$-language $L\left(𝒜\right)$ is not determined by ZFC: (1) There is a model $V_1$ of ZFC in which $L{\left(𝒜\right)}^{-}$ is countable. (2) There is a model $V_2$ of ZFC in which $L{\left(𝒜\right)}^{-}$ has cardinal $2^{{\aleph }_0}$. (3) There is a model $V_3$ of ZFC in which $L{\left(𝒜\right)}^{-}$ 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üchi automaton ℬ. 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üchi 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).

Détail

DOI : 10.1051/ita/2011113

Classification : 68Q45, 68Q15, 03D05, 03D10
Keywords: automata and formal languages, logic in computer science, computational complexity, infinite words, ω-languages, 1-counter automaton, 2-tape automaton, cardinality problems, decision problems, analytical hierarchy, largest thin effective coanalytic set, models of set theory, independence from the axiomatic system ZFC