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

Équipe de Logique Mathématique, Institut de Mathématiques de Jussieu, CNRS et Université Paris 7, France

finkel@logique.jussieu.fr

Received: 16 April 2010

Accepted: 4 July 2011

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 *ω*-language 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 of the *ω*-language is not determined by **ZFC**: (1) There is a model *V*_{1} of **ZFC **in which is countable. (2) There is a model *V*_{2} of **ZFC **in which has cardinal 2^{ℵ0}. (3) There is a model *V*_{3} of **ZFC **in which has cardinal ℵ_{1} with ℵ_{0} *<* ℵ_{1} *<* 2^{ℵ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 *ω*-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 *ω*-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 *ω*-language (respectively, infinitary rational relation) is countable is in Σ^{1}_{3}\(Π^{1}_{2} ∪ Σ^{1}_{2}).
This is rather surprising if compared to the fact that it is **decidable **whether an infinitary rational relation is countable (respectively, uncountable).

Mathematics Subject Classification: 68Q45 / 68Q15 / 03D05 / 03D10

Key words: 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**

*© EDP Sciences 2011*