# Hierarchies and reducibilities on regular languages related to modulo counting

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

- Volume: 43, Issue: 1, page 95-132
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topSelivanov, Victor L.. "Hierarchies and reducibilities on regular languages related to modulo counting." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 43.1 (2009): 95-132. <http://eudml.org/doc/245500>.

@article{Selivanov2009,

abstract = {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.},

author = {Selivanov, Victor L.},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {regular language; quasi-aperiodic regular language; quantifier-alternation hierarchy; difference hierarchy; polylogtime reducibility; quantifier-free reducibility; forbidden pattern; finite structures; complexity classes},

language = {eng},

number = {1},

pages = {95-132},

publisher = {EDP-Sciences},

title = {Hierarchies and reducibilities on regular languages related to modulo counting},

url = {http://eudml.org/doc/245500},

volume = {43},

year = {2009},

}

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

PB - EDP-Sciences

VL - 43

IS - 1

SP - 95

EP - 132

AB - 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.

LA - eng

KW - regular language; quasi-aperiodic regular language; quantifier-alternation hierarchy; difference hierarchy; polylogtime reducibility; quantifier-free reducibility; forbidden pattern; finite structures; complexity classes

UR - http://eudml.org/doc/245500

ER -

## References

top- [1] B. Borchert, On the acceptance power of regular languages. Theor. Comput. Sci. 148 (1995) 207–225. Zbl0873.68121MR1355587
- [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. Zbl0949.03035MR1728426
- [3] D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theor. Comput. Sci. 104 (1992) 263–283. Zbl0754.68049MR1186181
- [4] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logic Grundl. Math. 6 (1960) 66–92. Zbl0103.24705MR125010
- [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. Zbl0757.68057MR1163944
- [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. Zbl0893.68070MR1488396
- [7] R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci. 5 (1971) 1–16. Zbl0217.29602MR309676
- [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. Zbl1143.68048MR2217828
- [9] S. Eilenberg, Automata, Languages and Machines v. A and B. Academic Press (1974 and 1976). Zbl0317.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. Zbl1027.68074MR1990143
- [11] Z. Esik and K.G. Larsen, Regular languages definable by Lindström quantifiers. RAIRO-Theor. Inf. Appl. 37 (2003) 179–241. Zbl1046.20042MR2021315
- [12] C. Glaßer, Polylogtime-reductions decrease dot-depth, in Proc. of STACS-2005. Lect. Notes Comput. Sci. 3404 (2005). Zbl1118.68523
- [13] C. Glaßer, Languages Polylog-Time Reducible to Dot-Depth 1/2. J. Comput. System Sci. 73 (2007) 36–56. Zbl1178.68315MR2279030
- [14] C. Glaßer and H. Schmitz, The Boolean Structure of Dot-Depth One. J. Autom. Lang. Comb. 6 (2001) 437–452. Zbl1013.68112MR1897053
- [15] T. Gundermann and G. Wechsung, Counting classes of finite accepting types. Computers and Artificial Intelligence 6 (1987) 395–409. Zbl0638.68027MR974644
- [16] T. Gundermann, N.A. Nasser and G. Wechsung, A survey on counting classes, in Proc. of Structures in Complexity Theory (1990) 140–153. MR1097665
- [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. MR1310801
- [18] A.S. Kechris, Classical Descriptive Set Theory. Springer, New York (1994). Zbl0819.04002MR1321597
- [19] R. McNaughton, Algebraic decision procedures for local testability. Math. Syst. Theor. 8 (1974) 60–76. Zbl0287.02022MR392544
- [20] R. McNaughton and S. Papert, Counter-Free Automata. MIT Press, Cambridge, Massachussets (1971). Zbl0232.94024MR371538
- [21] J.-E. Pin, Varieties of Formal Languages. North Oxford Academic (1986). Zbl0655.68095MR912694
- [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. MR1470002
- [23] D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci. 32 (1986) 393–496. Zbl0618.03015MR858236
- [24] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theor. Comput. Syst. 30 (1997) 383–422. Zbl0872.68119MR1450862
- [25] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190–194. Zbl0131.02001MR176883
- [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. Zbl0976.03042MR1892340
- [27] V.L. Selivanov, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO-Theor. Inf. Appl. 36 (2002) 29–42. Zbl1029.03027MR1928157
- [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. Zbl1115.03045
- [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. Zbl1155.03310MR2380448
- [31] J. Shoenfield, Mathematical Logic. Addison Wesley, Massachussets (1967). Zbl0155.01102MR225631
- [32] A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems, Novosibirsk 161 (1998) 141–155 (in Russian). Zbl0932.03053MR1778013
- [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. Zbl0604.68066MR785905
- [35] H. Straubing, Finite automata, formal logic and circuit complexity. Birkhäuser, Boston (1994). Zbl0816.68086MR1269544
- [36] H. Straubing, On logical description of regular languages, in Proc. of LATIN-2002. Lect. Notes Comput. Sci. 2286 (2002) 528–538. Zbl1059.03034MR1966148
- [37] H. Straubing, D. Thérien and W. Thomas, Regular languages defined with generalized quantifiers. Inform. Comput. 118 (1995) 289–301. Zbl0826.68072MR1331729
- [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. Zbl1097.03035MR2143187
- [39] V.L. Selivanov and K.W. Wagner, A reducibility for the dot-depth hierarchy. Theor. Comput. Sci. 345 (2005) 448–472. Zbl1079.03028MR2171624
- [40] W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360–376. Zbl0503.68055MR684265
- [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. Zbl0558.68064MR792490
- [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. Zbl0084.01101MR98687
- [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). Zbl0822.68035MR1230967
- [44] K.W. Wagner, On $\omega $-regular sets. Inform. Control 43 (1979) 123–177. Zbl0434.68061MR553694
- [45] K.W. Wagner, Leaf language classes. MCU-2004. Lect. Notes Comput. Sci. 3354 (2005) 60–81. Zbl1119.68091MR2178402
- [46] T. Wilke, Classifying discrete temporal properties, in Proc. STACS-99. Lect. Notes Comput. Sci. 1563 (1999) 32–46. Zbl0926.03018MR1734035

## NotesEmbed ?

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