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.
Mots-clés : regular language, quasi-aperiodic regular language, quantifier-alternation hierarchy, difference hierarchy, polylogtime reducibility, quantifier-free reducibility, forbidden pattern
@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}, pages = {95--132}, publisher = {EDP-Sciences}, volume = {43}, number = {1}, year = {2009}, doi = {10.1051/ita:2007063}, mrnumber = {2483446}, zbl = {1174.03016}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/ita:2007063/} }
TY - JOUR AU - Selivanov, Victor L. TI - Hierarchies and reducibilities on regular languages related to modulo counting JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2009 SP - 95 EP - 132 VL - 43 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2007063/ DO - 10.1051/ita:2007063 LA - en ID - ITA_2009__43_1_95_0 ER -
%0 Journal Article %A Selivanov, Victor L. %T Hierarchies and reducibilities on regular languages related to modulo counting %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2009 %P 95-132 %V 43 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2007063/ %R 10.1051/ita:2007063 %G en %F 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) no. 1, pp. 95-132. doi : 10.1051/ita:2007063. http://archive.numdam.org/articles/10.1051/ita:2007063/
[1] On the acceptance power of regular languages. Theor. Comput. Sci. 148 (1995) 207-225. | MR | Zbl
,[2] On existentially first-order definable languages and their relation to . RAIRO-Theor. Inf. Appl. 33 (1999) 259-269. | Numdam | MR | Zbl
, and ,[3] A uniform approach to define complexity classes. Theor. Comput. Sci. 104 (1992) 263-283. | MR | Zbl
, and ,[4] Weak second-order arithmetic and finite automata. Z. Math. Logic Grundl. Math. 6 (1960) 66-92. | MR | Zbl
,[5] Regular languages in . J. Comput. System Sci. 44 (1992) 478-499. | MR | Zbl
, , and ,[6] The chain method to separate counting classes. Theor. Comput. Syst. 31 (1998) 93-108. | MR | Zbl
, , and ,[7] Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1-16. | MR | Zbl
and ,[8] Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci. 356 (2006) 73-89. | MR | Zbl
, and ,[9] Automata, Languages and Machines v. A and B. Academic Press (1974 and 1976). | Zbl
,[10] Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybern. 16 (2003) 1-28. | MR | Zbl
and ,[11] Regular languages definable by Lindström quantifiers. RAIRO-Theor. Inf. Appl. 37 (2003) 179-241. | Numdam | MR | Zbl
and ,[12] Polylogtime-reductions decrease dot-depth, in Proc. of STACS-2005. Lect. Notes Comput. Sci. 3404 (2005). | Zbl
,[13] Languages Polylog-Time Reducible to Dot-Depth 1/2. J. Comput. System Sci. 73 (2007) 36-56. | MR | Zbl
,[14] The Boolean Structure of Dot-Depth One. J. Autom. Lang. Comb. 6 (2001) 437-452. | MR | Zbl
and ,[15] Counting classes of finite accepting types. Computers and Artificial Intelligence 6 (1987) 395-409. | MR | Zbl
and ,[16] A survey on counting classes, in Proc. of Structures in Complexity Theory (1990) 140-153. | MR
, and ,[17] On the power of polynomial time bit-reductions, Proc. 8th Structure in Complexity Theory (1993) 200-207. | MR
, , , and ,[18] Classical Descriptive Set Theory. Springer, New York (1994). | MR | Zbl
,[19] Algebraic decision procedures for local testability. Math. Syst. Theor. 8 (1974) 60-76. | MR | Zbl
,[20] Counter-Free Automata. MIT Press, Cambridge, Massachussets (1971). | MR | Zbl
and ,[21] Varieties of Formal Languages. North Oxford Academic (1986). | MR | Zbl
,[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
,[23] First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393-496. | MR | Zbl
and ,[24] Polynomial closure and unambiguous product. Theor. Comput. Syst. 30 (1997) 383-422. | MR | Zbl
and ,[25] On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190-194. | MR | Zbl
,[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 | Zbl
,[27] Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO-Theor. Inf. Appl. 36 (2002) 29-42. | Numdam | MR | Zbl
,[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
,[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 | Zbl
,[31] Mathematical Logic. Addison Wesley, Massachussets (1967). | MR | Zbl
,[32] Difference hierarchies of regular languages. Comput. Systems, Novosibirsk 161 (1998) 141-155 (in Russian). | MR | Zbl
,[33] On hierarchies of regular star-free languages (in Russian). Preprint 69 of A.P. Ershov Institute of Informatics Systems (2000) 28.
and ,[34] Characterizations of some classes of regular events. Theor. Comput. Sci. 35 (1985) 163-176. | MR | Zbl
,[35] Finite automata, formal logic and circuit complexity. Birkhäuser, Boston (1994). | MR | Zbl
,[36] On logical description of regular languages, in Proc. of LATIN-2002. Lect. Notes Comput. Sci. 2286 (2002) 528-538. | MR | Zbl
,[37] Regular languages defined with generalized quantifiers. Inform. Comput. 118 (1995) 289-301. | MR | Zbl
, and ,[38] 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 | Zbl
and ,[39] A reducibility for the dot-depth hierarchy. Theor. Comput. Sci. 345 (2005) 448-472. | MR | Zbl
and ,[40] Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360-376. | MR | Zbl
,[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 | Zbl
,[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 | Zbl
,[43] Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk 57 (1993) 51-90 (in Russian). | MR | Zbl
,[44] On -regular sets. Inform. Control 43 (1979) 123-177. | MR | Zbl
,[45] Leaf language classes. MCU-2004. Lect. Notes Comput. Sci. 3354 (2005) 60-81. | MR | Zbl
,[46] Classifying discrete temporal properties, in Proc. STACS-99. Lect. Notes Comput. Sci. 1563 (1999) 32-46. | MR | Zbl
,Cité par Sources :