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.
@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] , On the acceptance power of regular languages. Theor. Comput. Sci. 148 (1995) 207-225. | MR 1355587 | Zbl 0873.68121
[2] , and , On existentially first-order definable languages and their relation to . RAIRO-Theor. Inf. Appl. 33 (1999) 259-269. | Numdam | MR 1728426 | Zbl 0949.03035
[3] , and , A uniform approach to define complexity classes. Theor. Comput. Sci. 104 (1992) 263-283. | MR 1186181 | Zbl 0754.68049
[4] , Weak second-order arithmetic and finite automata. Z. Math. Logic Grundl. Math. 6 (1960) 66-92. | MR 125010 | Zbl 0103.24705
[5] , , and , Regular languages in . J. Comput. System Sci. 44 (1992) 478-499. | MR 1163944 | Zbl 0757.68057
[6] , , and , The chain method to separate counting classes. Theor. Comput. Syst. 31 (1998) 93-108. | MR 1488396 | Zbl 0893.68070
[7] and , Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-16. | MR 309676 | Zbl 0217.29602
[8] , and , Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci. 356 (2006) 73-89. | MR 2217828 | Zbl 1143.68048
[9] , Automata, Languages and Machines v. A and B. Academic Press (1974 and 1976). | Zbl 0317.94045
[10] and , 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] and , Regular languages definable by Lindström quantifiers. RAIRO-Theor. Inf. Appl. 37 (2003) 179-241. | Numdam | MR 2021315 | Zbl 1046.20042
[12] , Polylogtime-reductions decrease dot-depth, in Proc. of STACS-2005. Lect. Notes Comput. Sci. 3404 (2005). | Zbl 1118.68523
[13] , Languages Polylog-Time Reducible to Dot-Depth 1/2. J. Comput. System Sci. 73 (2007) 36-56. | MR 2279030 | Zbl 1178.68315
[14] and , The Boolean Structure of Dot-Depth One. J. Autom. Lang. Comb. 6 (2001) 437-452. | MR 1897053 | Zbl 1013.68112
[15] and , Counting classes of finite accepting types. Computers and Artificial Intelligence 6 (1987) 395-409. | MR 974644 | Zbl 0638.68027
[16] , and , A survey on counting classes, in Proc. of Structures in Complexity Theory (1990) 140-153. | MR 1097665
[17] , , , and , On the power of polynomial time bit-reductions, Proc. 8th Structure in Complexity Theory (1993) 200-207. | MR 1310801
[18] , Classical Descriptive Set Theory. Springer, New York (1994). | MR 1321597 | Zbl 0819.04002
[19] , Algebraic decision procedures for local testability. Math. Syst. Theor. 8 (1974) 60-76. | MR 392544 | Zbl 0287.02022
[20] and , Counter-Free Automata. MIT Press, Cambridge, Massachussets (1971). | MR 371538 | Zbl 0232.94024
[21] , Varieties of Formal Languages. North Oxford Academic (1986). | MR 912694 | Zbl 0655.68095
[22] , 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] and , First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393-496. | MR 858236 | Zbl 0618.03015
[24] and , Polynomial closure and unambiguous product. Theor. Comput. Syst. 30 (1997) 383-422. | MR 1450862 | Zbl 0872.68119
[25] , On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190-194. | MR 176883 | Zbl 0131.02001
[26] , 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] , Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO-Theor. Inf. Appl. 36 (2002) 29-42. | Numdam | MR 1928157 | Zbl 1029.03027
[28] , Some hierarchies and reducibilities on regular languages. University of Würzburg, Technical Report 349 (2004).
[29] , Some reducibilities on regular sets, in Proc. of CIE-2005. Lect. Notes Comput. Sci. 3526 (2005) 430-440. | Zbl 1115.03045
[30] , 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] , Mathematical Logic. Addison Wesley, Massachussets (1967). | MR 225631 | Zbl 0155.01102
[32] , Difference hierarchies of regular languages. Comput. Systems, Novosibirsk 161 (1998) 141-155 (in Russian). | MR 1778013 | Zbl 0932.03053
[33] and , On hierarchies of regular star-free languages (in Russian). Preprint 69 of A.P. Ershov Institute of Informatics Systems (2000) 28.
[34] , Characterizations of some classes of regular events. Theor. Comput. Sci. 35 (1985) 163-176. | MR 785905 | Zbl 0604.68066
[35] , Finite automata, formal logic and circuit complexity. Birkhäuser, Boston (1994). | MR 1269544 | Zbl 0816.68086
[36] , 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] , and , Regular languages defined with generalized quantifiers. Inform. Comput. 118 (1995) 289-301. | MR 1331729 | Zbl 0826.68072
[38] and , 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] and , A reducibility for the dot-depth hierarchy. Theor. Comput. Sci. 345 (2005) 448-472. | MR 2171624 | Zbl 1079.03028
[40] , Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360-376. | MR 684265 | Zbl 0503.68055
[41] , 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] , 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] , 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] , On -regular sets. Inform. Control 43 (1979) 123-177. | MR 553694 | Zbl 0434.68061
[45] , Leaf language classes. MCU-2004. Lect. Notes Comput. Sci. 3354 (2005) 60-81. | MR 2178402 | Zbl 1119.68091
[46] , Classifying discrete temporal properties, in Proc. STACS-99. Lect. Notes Comput. Sci. 1563 (1999) 32-46. | MR 1734035 | Zbl 0926.03018