Hierarchies and reducibilities on regular languages related to modulo counting
Selivanov, Victor L.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009), p. 95-132 / Harvested from Numdam

We discuss some known and introduce some new hierarchies and reducibilities on regular languages, with the emphasis on the quantifier-alternation and difference hierarchies of the quasi-aperiodic languages. The non-collapse of these hierarchies and decidability of some levels are established. Complete sets in the levels of the hierarchies under the polylogtime and some quantifier-free reducibilities are found. Some facts about the corresponding degree structures are established. As an application, we characterize the regular languages whose balanced leaf-language classes are contained in the polynomial hierarchy. For any discussed reducibility we try to give motivations and open questions, in a hope to convince the reader that the study of these reducibilities is interesting for automata theory and computational complexity.

Publié le : 2009-01-01
DOI : https://doi.org/10.1051/ita:2007063
Classification:  03D05,  03C13,  68Q15
@article{ITA_2009__43_1_95_0,
     author = {Selivanov, Victor L.},
     title = {Hierarchies and reducibilities on regular languages related to modulo counting},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {43},
     year = {2009},
     pages = {95-132},
     doi = {10.1051/ita:2007063},
     mrnumber = {2483446},
     zbl = {1174.03016},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2009__43_1_95_0}
}
Selivanov, Victor L. Hierarchies and reducibilities on regular languages related to modulo counting. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) pp. 95-132. doi : 10.1051/ita:2007063. http://gdmltest.u-ga.fr/item/ITA_2009__43_1_95_0/

[1] B. Borchert, On the acceptance power of regular languages. Theor. Comput. Sci. 148 (1995) 207-225. | MR 1355587 | Zbl 0873.68121

[2] B. Borchert, D. Kuske and F. Stephan, On existentially first-order definable languages and their relation to NP. RAIRO-Theor. Inf. Appl. 33 (1999) 259-269. | Numdam | MR 1728426 | Zbl 0949.03035

[3] D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theor. Comput. Sci. 104 (1992) 263-283. | MR 1186181 | Zbl 0754.68049

[4] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logic Grundl. Math. 6 (1960) 66-92. | MR 125010 | Zbl 0103.24705

[5] D.A.M. Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC 1 . J. Comput. System Sci. 44 (1992) 478-499. | MR 1163944 | Zbl 0757.68057

[6] K. Cronauer, U. Hertrampf, H. Vollmer and K.W. Wagner, The chain method to separate counting classes. Theor. Comput. Syst. 31 (1998) 93-108. | MR 1488396 | Zbl 0893.68070

[7] R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-16. | MR 309676 | Zbl 0217.29602

[8] L. Chaubard, J.-E. Pin and H. Straubing, Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci. 356 (2006) 73-89. | MR 2217828 | Zbl 1143.68048

[9] S. Eilenberg, Automata, Languages and Machines v. A and B. Academic Press (1974 and 1976). | Zbl 0317.94045

[10] Z. Esik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybern. 16 (2003) 1-28. | MR 1990143 | Zbl 1027.68074

[11] Z. Esik and K.G. Larsen, Regular languages definable by Lindström quantifiers. RAIRO-Theor. Inf. Appl. 37 (2003) 179-241. | Numdam | MR 2021315 | Zbl 1046.20042

[12] C. Glaßer, Polylogtime-reductions decrease dot-depth, in Proc. of STACS-2005. Lect. Notes Comput. Sci. 3404 (2005). | Zbl 1118.68523

[13] C. Glaßer, Languages Polylog-Time Reducible to Dot-Depth 1/2. J. Comput. System Sci. 73 (2007) 36-56. | MR 2279030 | Zbl 1178.68315

[14] C. Glaßer and H. Schmitz, The Boolean Structure of Dot-Depth One. J. Autom. Lang. Comb. 6 (2001) 437-452. | MR 1897053 | Zbl 1013.68112

[15] T. Gundermann and G. Wechsung, Counting classes of finite accepting types. Computers and Artificial Intelligence 6 (1987) 395-409. | MR 974644 | Zbl 0638.68027

[16] T. Gundermann, N.A. Nasser and G. Wechsung, A survey on counting classes, in Proc. of Structures in Complexity Theory (1990) 140-153. | MR 1097665

[17] U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer and K.W. Wagner, On the power of polynomial time bit-reductions, Proc. 8th Structure in Complexity Theory (1993) 200-207. | MR 1310801

[18] A.S. Kechris, Classical Descriptive Set Theory. Springer, New York (1994). | MR 1321597 | Zbl 0819.04002

[19] R. Mcnaughton, Algebraic decision procedures for local testability. Math. Syst. Theor. 8 (1974) 60-76. | MR 392544 | Zbl 0287.02022

[20] R. Mcnaughton and S. Papert, Counter-Free Automata. MIT Press, Cambridge, Massachussets (1971). | MR 371538 | Zbl 0232.94024

[21] J.-E. Pin, Varieties of Formal Languages. North Oxford Academic (1986). | MR 912694 | Zbl 0655.68095

[22] J.-E. Pin, Syntactic semigroups, Chap. 10 in Handbook of language theory, Vol. I, edited by G. Rozenberg and A. Salomaa. Springer Verlag (1997) 679-746. | MR 1470002

[23] D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393-496. | MR 858236 | Zbl 0618.03015

[24] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theor. Comput. Syst. 30 (1997) 383-422. | MR 1450862 | Zbl 0872.68119

[25] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190-194. | MR 176883 | Zbl 0131.02001

[26] V.L. Selivanov, A logical approach to decidability of hierarchies of regular star-free languages, in Proc. of STACS-2001. Lect. Notes Comput. Sci. 2010 (2001) 539-550. | MR 1892340 | Zbl 0976.03042

[27] V.L. Selivanov, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO-Theor. Inf. Appl. 36 (2002) 29-42. | Numdam | MR 1928157 | Zbl 1029.03027

[28] V.L. Selivanov, Some hierarchies and reducibilities on regular languages. University of Würzburg, Technical Report 349 (2004).

[29] V.L. Selivanov, Some reducibilities on regular sets, in Proc. of CIE-2005. Lect. Notes Comput. Sci. 3526 (2005) 430-440. | Zbl 1115.03045

[30] V.L. Selivanov, Fine hierarchy of regular aperiodic ω-languages, in Proc. of DLT-2007, edited by T. Harju, J. Karhumäki and A. Lepistö. Lect. Notes Comput. Sci. 4588 (2007) 399-410. | MR 2380448 | Zbl 1155.03310

[31] J. Shoenfield, Mathematical Logic. Addison Wesley, Massachussets (1967). | MR 225631 | Zbl 0155.01102

[32] A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems, Novosibirsk 161 (1998) 141-155 (in Russian). | MR 1778013 | Zbl 0932.03053

[33] V.L. Selivanov and A.G. Shukin, On hierarchies of regular star-free languages (in Russian). Preprint 69 of A.P. Ershov Institute of Informatics Systems (2000) 28.

[34] J. Stern, Characterizations of some classes of regular events. Theor. Comput. Sci. 35 (1985) 163-176. | MR 785905 | Zbl 0604.68066

[35] H. Straubing, Finite automata, formal logic and circuit complexity. Birkhäuser, Boston (1994). | MR 1269544 | Zbl 0816.68086

[36] H. Straubing, On logical description of regular languages, in Proc. of LATIN-2002. Lect. Notes Comput. Sci. 2286 (2002) 528-538. | MR 1966148 | Zbl 1059.03034

[37] H. Straubing, D. Thérien and W. Thomas, Regular languages defined with generalized quantifiers. Inform. Comput. 118 (1995) 289-301. | MR 1331729 | Zbl 0826.68072

[38] V.L. Selivanov and K.W. Wagner, A reducibility for the dot-depth hierarchy. Proc. 29th Int. Symp. on Mathematical Foundations of Computer Science. Lect. Notes Comput. Sci. 3153 (2004) 783-793. | MR 2143187 | Zbl 1097.03035

[39] V.L. Selivanov and K.W. Wagner, A reducibility for the dot-depth hierarchy. Theor. Comput. Sci. 345 (2005) 448-472. | MR 2171624 | Zbl 1079.03028

[40] W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360-376. | MR 684265 | Zbl 0503.68055

[41] W. Thomas, An application of the Ehrenteucht-Fraïssé game in formal language theory. Mém. Soc. Math. France Ser. 2 16 (1984) 11-21. | Numdam | MR 792490 | Zbl 0558.68064

[42] B.A. Trakhtenbrot, Synthesis of logic networks whose operators are described by means of single-placed predicate calculus. Doklady Akad. Nauk SSSR 118 (1958) 646-649. | MR 98687 | Zbl 0084.01101

[43] N.K. Vereshchagin, Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk 57 (1993) 51-90 (in Russian). | MR 1230967 | Zbl 0822.68035

[44] K.W. Wagner, On ω-regular sets. Inform. Control 43 (1979) 123-177. | MR 553694 | Zbl 0434.68061

[45] K.W. Wagner, Leaf language classes. MCU-2004. Lect. Notes Comput. Sci. 3354 (2005) 60-81. | MR 2178402 | Zbl 1119.68091

[46] T. Wilke, Classifying discrete temporal properties, in Proc. STACS-99. Lect. Notes Comput. Sci. 1563 (1999) 32-46. | MR 1734035 | Zbl 0926.03018