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) no. 1, pp. 95-132.

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.

Classification : 03D05, 03C13, 68Q15
Mots clés : regular language, quasi-aperiodic regular language, quantifier-alternation hierarchy, difference hierarchy, polylogtime reducibility, quantifier-free reducibility, forbidden pattern

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

[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 | Zbl

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

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

[5] D.A.M. Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in $N{C}^1$. J. Comput. System Sci. 44 (1992) 478-499. | MR | Zbl

[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 | Zbl

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

[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 | Zbl

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

[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 | Zbl

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

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

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

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

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

[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

[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

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

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

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

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

[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

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

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

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

[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 | Zbl

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

[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

[30] V.L. Selivanov, Fine hierarchy of regular aperiodic $\omega$-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] J. Shoenfield, Mathematical Logic. Addison Wesley, Massachussets (1967). | MR | Zbl

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

[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 | Zbl

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

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

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

[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 | Zbl

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

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

[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 | Zbl

[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 | Zbl

[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 | Zbl

[44] K.W. Wagner, On $\omega$-regular sets. Inform. Control 43 (1979) 123-177. | MR | Zbl

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

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