×

Some problems in automata theory which depend on the models of set theory. (English) Zbl 1232.68082

Summary: 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(\mathcal A)\) accepted by a Büchi 1-counter automaton \(\mathcal A\). We prove the following surprising result: there exists a 1-counter Büchi automaton \(\mathcal A\) such that the cardinality of the complement \(L(\mathcal A)^{ - }\) of the \(\omega \)-language \(L(\mathcal A)\) is not determined by ZFC: (1) There is a model \(V_{1}\) of ZFC in which \(L(\mathcal A)^{ - }\) is countable. (2) There is a model \(V_{2}\) of ZFC in which \(L(\mathcal A)^{ - }\) has cardinal \(2^{\aleph_{0}}\). (3) There is a model \(V_{3}\) of ZFC in which \(L(\mathcal 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üchi automaton \(\mathcal 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ü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 ^{1}_{3}\setminus (\Pi ^{1}_{2} \cup \Sigma ^{1}_{2})\). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

MSC:

68Q45 Formal languages and automata
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
03D05 Automata and formal grammars in connection with logical questions
03D10 Turing machines and related notions
PDFBibTeX XMLCite
Full Text: DOI arXiv EuDML

References:

[1] J. Castro and F. Cucker, Nondeterministic \omega -computations and the analytical hierarchy. J. Math. Logik Grundl. Math.35 (1989) 333-342. Zbl0661.03030 · Zbl 0661.03030 · doi:10.1002/malq.19890350406
[2] R.S. Cohen and A.Y. Gold, \omega -computations on Turing machines. Theoret. Comput. Sci.6 (1978) 1-23. · Zbl 0368.68057 · doi:10.1016/0304-3975(78)90002-6
[3] O. Finkel, Borel ranks and Wadge degrees of omega context free languages. Math. Structures Comput. Sci.16 (2006) 813-840. Zbl1121.03047 · Zbl 1121.03047 · doi:10.1017/S0960129506005597
[4] O. Finkel, 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. Zbl1137.03023 · Zbl 1137.03023 · doi:10.1007/11672142_24
[5] O. Finkel, The complexity of infinite computations in models of set theory. Log. Meth. Comput. Sci.5 (2009) 1-19. Zbl1191.03034 · Zbl 1191.03034 · doi:10.2168/LMCS-5(4:4)2009
[6] O. Finkel, Highly undecidable problems for infinite computations. RAIRO - Theor. Inf. Appl.43 (2009) 339-364. Zbl1171.03024 · Zbl 1171.03024 · doi:10.1051/ita/2009001
[7] O. Finkel, 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. Notes196 (2010) 127-151.
[8] F. Gire, Relations rationnelles infinitaires. Ph.D. thesis, Université Paris VII (1981). · Zbl 0552.68064
[9] F. Gire and M. Nivat, Relations rationnelles infinitaires. CalcoloXXI (1984) 91-125. · Zbl 0552.68064 · doi:10.1007/BF02575909
[10] E. Grädel, W. Thomas and W. Wilke Eds., Automata, Logics, and Infinite Games : A Guide to Current Research [outcome of a Dagstuhl seminar, February 2001]. Lect. Notes Comput. Sci.2500 (2002).
[11] Y. Gurevich, M. Magidor and S. Shelah, The monadic theory of \omega 2. J. Symbolic Logic48 (1983) 387-398. · Zbl 0549.03010 · doi:10.2307/2273556
[12] J.E. Hopcroft, R. Motwani and J.D. Ullman, Introduction to automata theory, languages, and computation. Addison-Wesley Publishing Co., Reading, Mass. Addison-Wesley Series in Computer Science (2001). Zbl0980.68066 · Zbl 0980.68066
[13] T. Jech, Set Theory, 3rd edition. Springer (2002).
[14] A. Kanamori, The Higher Infinite. Springer-Verlag (1997). · Zbl 0903.03030
[15] A.S. Kechris, The theory of countable analytical sets. Trans. Amer. Math. Soc.202 (1975) 259-297. · Zbl 0317.02082 · doi:10.2307/1997311
[16] D. Kuske and M. Lohrey, First-order and counting theories of omega-automatic structures. J. Symbolic Logic73 (2008) 129-150. · Zbl 1141.03015 · doi:10.2178/jsl/1208358745
[17] L.H. Landweber, Decision problems for \omega -automata. Math. Syst. Theor.3 (1969) 376-384. · Zbl 0182.02402 · doi:10.1007/BF01691063
[18] H. Lescow and W. Thomas, 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.
[19] Y.N. Moschovakis, Descriptive set theory. North-Holland Publishing Co., Amsterdam (1980).
[20] I. Neeman, Finite state automata and monadic definability of singular cardinals. J. Symbolic Logic73 (2008) 412-438. · Zbl 1148.03030 · doi:10.2178/jsl/1208359052
[21] D. Niwinski, 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. Zbl0776.68086 · Zbl 0776.68086
[22] D. Perrin and J.-E. Pin, Infinite words, automata, semigroups, logic and games. Pure Appl. Math.141 (2004). · Zbl 1094.68052
[23] H. Rogers, Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967). Zbl0183.01401 · Zbl 0183.01401
[24] L. Staiger, Hierarchies of recursive \omega -languages. Elektronische Informationsverarbeitung und Kybernetik22 (1986) 219-241. · Zbl 0627.03024
[25] L. Staiger, \omega -languages, in Handbook of formal languages3. Springer, Berlin (1997) 339-387.
[26] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer ScienceB, Formal models and semantics. J. van Leeuwen, Ed. Elsevier (1990) 135-191. · Zbl 0900.68316
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.