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 of ZFC in which is countable. (2) There is a model of ZFC in which has cardinal . (3) There is a model of ZFC in which has cardinal with . 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 . This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).
Mots-clés : 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
@article{ITA_2011__45_4_383_0, author = {Finkel, Olivier}, title = {Some problems in automata theory which depend on the models of set theory}, journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications}, pages = {383--397}, publisher = {EDP-Sciences}, volume = {45}, number = {4}, year = {2011}, doi = {10.1051/ita/2011113}, mrnumber = {2876113}, zbl = {1232.68082}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita/2011113/} }
TY - JOUR AU - Finkel, Olivier TI - Some problems in automata theory which depend on the models of set theory JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2011 SP - 383 EP - 397 VL - 45 IS - 4 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2011113/ DO - 10.1051/ita/2011113 LA - en ID - ITA_2011__45_4_383_0 ER -
%0 Journal Article %A Finkel, Olivier %T Some problems in automata theory which depend on the models of set theory %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2011 %P 383-397 %V 45 %N 4 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2011113/ %R 10.1051/ita/2011113 %G en %F ITA_2011__45_4_383_0
Finkel, Olivier. Some problems in automata theory which depend on the models of set theory. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 45 (2011) no. 4, pp. 383-397. doi : 10.1051/ita/2011113. http://archive.numdam.org/articles/10.1051/ita/2011113/
[1] Nondeterministic ω-computations and the analytical hierarchy. J. Math. Logik Grundl. Math. 35 (1989) 333-342. | MR | Zbl
and ,[2] ω-computations on Turing machines. Theoret. Comput. Sci. 6 (1978) 1-23. | MR | Zbl
and ,[3] Borel ranks and Wadge degrees of omega context free languages. Math. Structures Comput. Sci. 16 (2006) 813-840. | MR | Zbl
,[4] On the accepting power of two-tape Büchi automata, in Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science. STACS 2006. Lect. Notes Comput. Sci. 3884 (2006) 301-312. | MR | Zbl
,[5] The complexity of infinite computations in models of set theory. Log. Meth. Comput. Sci. 5 (2009) 1-19. | MR | Zbl
,[6] Highly undecidable problems for infinite computations. RAIRO - Theor. Inf. Appl. 43 (2009) 339-364. | Numdam | MR | Zbl
,[7] Decision problems for recognizable languages of infinite pictures, in Studies in Weak Arithmetics, Proceedings of the International Conference 28th Weak Arithmetic Days, 2009, Publications of the Center for the Study of Language and Information. Lect. Notes 196 (2010) 127-151. | MR | Zbl
,[8] Relations rationnelles infinitaires. Ph.D. thesis, Université Paris VII (1981). | Zbl
,[9] Relations rationnelles infinitaires. Calcolo XXI (1984) 91-125. | MR | Zbl
and ,[10] Automata, Logics, and Infinite Games : A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Lect. Notes Comput. Sci. 2500 (2002). | MR | Zbl
, and Eds.,[11] The monadic theory of ω2. J. Symbolic Logic 48 (1983) 387-398. | MR | Zbl
, and ,[12] Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass. Addison-Wesley Series in Computer Science (2001). | MR | Zbl
, and ,[13] Set Theory, 3rd edition. Springer (2002). | MR | Zbl
,[14] The Higher Infinite. Springer-Verlag (1997). | Zbl
,[15] The theory of countable analytical sets. Trans. Amer. Math. Soc. 202 (1975) 259-297. | MR | Zbl
,[16] First-order and counting theories of omega-automatic structures. J. Symbolic Logic 73 (2008) 129-150. | MR | Zbl
and ,[17] Decision problems for ω-automata. Math. Syst. Theor. 3 (1969) 376-384. | MR | Zbl
,[18] Logical specifications of infinite computations, in A Decade of Concurrency, J.W. de Bakker, W.P. de Roever and G. Rozenberg, Eds. Lect. Notes Comput. Sci. 803 (1994) 583-621. | MR
and ,[19] Descriptive set theory. North-Holland Publishing Co., Amsterdam (1980). | MR | Zbl
,[20] Finite state automata and monadic definability of singular cardinals. J. Symbolic Logic 73 (2008) 412-438. | MR | Zbl
,[21] On the cardinality of sets of infinite trees recognizable by finite automata, in Proceedings of the International Conference MFCS. Lect. Notes Comput. Sci. 520 (1991) 367-376. | MR | Zbl
,[22] Infinite words, automata, semigroups, logic and games. Pure Appl. Math. 141 (2004). | Zbl
and ,[23] Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967). | MR | Zbl
,[24] Hierarchies of recursive ω-languages. Elektronische Informationsverarbeitung und Kybernetik 22 (1986) 219-241. | MR | Zbl
,[25] ω-languages, in Handbook of formal languages 3. Springer, Berlin (1997) 339-387. | MR
,[26] Automata on infinite objects, in Handbook of Theoretical Computer Science B, Formal models and semantics. J. van Leeuwen, Ed. Elsevier (1990) 135-191. | MR | Zbl
,Cité par Sources :