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

Olivier Finkel

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2011)

  • Volume: 45, Issue: 4, page 383-397
  • ISSN: 0988-3754

Abstract

top
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 L ( 𝒜 ) L(x1d49c;) accepted by a Büchi 1-counter automaton 𝒜 x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton 𝒜 x1d49c; such that the cardinality of the complement L ( 𝒜 ) - L(𝒜) −  of the ω-language L ( 𝒜 ) L(𝒜) is not determined by ZFC: (1) There is a model V1of ZFC in which L ( 𝒜 ) - L(𝒜) −  is countable. (2) There is a model V2of ZFC in which L ( 𝒜 ) - L(𝒜) −  has cardinal 2ℵ0. (3) There is a model V3of ZFC in which L ( 𝒜 ) - L(𝒜) −  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 Σ1312 ∪ Σ12). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).

How to cite

top

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 45.4 (2011): 383-397. <http://eudml.org/doc/273059>.

@article{Finkel2011,
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 ω-language $L(\mathcal \{A\})$L(x1d49c;) accepted by a Büchi 1-counter automaton $\mathcal \{A\}$x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton $\mathcal \{A\}$x1d49c; such that the cardinality of the complement $L(\mathcal \{A\})^-$L(&#x1d49c;) −  of the ω-language $L(\mathcal \{A\})$L(&#x1d49c;) is not determined by ZFC: (1) There is a model V1of ZFC in which $L(\mathcal \{A\})^-$L(&#x1d49c;) −  is countable. (2) There is a model V2of ZFC in which $L(\mathcal \{A\})^-$L(&#x1d49c;) −  has cardinal 2ℵ0. (3) There is a model V3of ZFC in which $L(\mathcal \{A\})^-$L(&#x1d49c;) −  has cardinal ℵ1 with ℵ0 &lt; ℵ1 &lt; 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 Σ1312 ∪ Σ12). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).},
author = {Finkel, Olivier},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
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; formal languages; -languages; axiomatic system ZFC; independence from ZFC},
language = {eng},
number = {4},
pages = {383-397},
publisher = {EDP-Sciences},
title = {Some problems in automata theory which depend on the models of set theory},
url = {http://eudml.org/doc/273059},
volume = {45},
year = {2011},
}

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
PB - EDP-Sciences
VL - 45
IS - 4
SP - 383
EP - 397
AB - 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 $L(\mathcal {A})$L(x1d49c;) accepted by a Büchi 1-counter automaton $\mathcal {A}$x1d49c;. We prove the following surprising result: there exists a 1-counter Büchi automaton $\mathcal {A}$x1d49c; such that the cardinality of the complement $L(\mathcal {A})^-$L(&#x1d49c;) −  of the ω-language $L(\mathcal {A})$L(&#x1d49c;) is not determined by ZFC: (1) There is a model V1of ZFC in which $L(\mathcal {A})^-$L(&#x1d49c;) −  is countable. (2) There is a model V2of ZFC in which $L(\mathcal {A})^-$L(&#x1d49c;) −  has cardinal 2ℵ0. (3) There is a model V3of ZFC in which $L(\mathcal {A})^-$L(&#x1d49c;) −  has cardinal ℵ1 with ℵ0 &lt; ℵ1 &lt; 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 Σ1312 ∪ Σ12). This is rather surprising if compared to the fact that it is decidable whether an infinitary rational relation is countable (respectively, uncountable).
LA - eng
KW - 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; formal languages; -languages; axiomatic system ZFC; independence from ZFC
UR - http://eudml.org/doc/273059
ER -

References

top
  1. [1] J. Castro and F. Cucker, Nondeterministic ω-computations and the analytical hierarchy. J. Math. Logik Grundl. Math.35 (1989) 333–342. Zbl0661.03030MR1020506
  2. [2] R.S. Cohen and A.Y. Gold, ω-computations on Turing machines. Theoret. Comput. Sci.6 (1978) 1–23. Zbl0368.68057MR465819
  3. [3] O. Finkel, Borel ranks and Wadge degrees of omega context free languages. Math. Structures Comput. Sci.16 (2006) 813–840. Zbl1121.03047MR2268344
  4. [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.03023MR2250991
  5. [5] O. Finkel, The complexity of infinite computations in models of set theory. Log. Meth. Comput. Sci.5 (2009) 1–19. Zbl1191.03034MR2575076
  6. [6] O. Finkel, Highly undecidable problems for infinite computations. RAIRO – Theor. Inf. Appl.43 (2009) 339–364. Zbl1171.03024MR2512263
  7. [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. Notes 196 (2010) 127–151. Zbl1244.03052MR2681800
  8. [8] F. Gire, Relations rationnelles infinitaires. Ph.D. thesis, Université Paris VII (1981). Zbl0552.68064
  9. [9] F. Gire and M. Nivat, Relations rationnelles infinitaires. Calcolo XXI (1984) 91–125. Zbl0552.68064MR799616
  10. [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). Zbl1011.00037MR2070731
  11. [11] Y. Gurevich, M. Magidor and S. Shelah, The monadic theory of ω2. J. Symbolic Logic48 (1983) 387–398. Zbl0549.03010MR704093
  12. [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.68066MR645539
  13. [13] T. Jech, Set Theory, 3rd edition. Springer (2002). Zbl1007.03002MR1492987
  14. [14] A. Kanamori, The Higher Infinite. Springer-Verlag (1997). Zbl0813.03034
  15. [15] A.S. Kechris, The theory of countable analytical sets. Trans. Amer. Math. Soc.202 (1975) 259–297. Zbl0317.02082MR419235
  16. [16] D. Kuske and M. Lohrey, First-order and counting theories of omega-automatic structures. J. Symbolic Logic73 (2008) 129–150. Zbl1141.03015MR2387935
  17. [17] L.H. Landweber, Decision problems for ω-automata. Math. Syst. Theor.3 (1969) 376–384. Zbl0182.02402MR260595
  18. [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. MR1292687
  19. [19] Y.N. Moschovakis, Descriptive set theory. North-Holland Publishing Co., Amsterdam (1980). Zbl0433.03025MR561709
  20. [20] I. Neeman, Finite state automata and monadic definability of singular cardinals. J. Symbolic Logic73 (2008) 412–438. Zbl1148.03030MR2414457
  21. [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.68086MR1135376
  22. [22] D. Perrin and J.-E. Pin, Infinite words, automata, semigroups, logic and games. Pure Appl. Math. 141 (2004). Zbl1094.68052
  23. [23] H. Rogers, Theory of Recursive Functions and Effective Computability. McGraw-Hill, New York (1967). Zbl0183.01401MR224462
  24. [24] L. Staiger, Hierarchies of recursive ω-languages. Elektronische Informationsverarbeitung und Kybernetik22 (1986) 219–241. Zbl0627.03024MR855527
  25. [25] L. Staiger, ω-languages, in Handbook of formal languages 3. Springer, Berlin (1997) 339–387. MR1470023
  26. [26] W. Thomas, Automata on infinite objects, in Handbook of Theoretical Computer Science B, Formal models and semantics. J. van Leeuwen, Ed. Elsevier (1990) 135–191. Zbl0900.68316MR1127189

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.