# Hierarchies and reducibilities on regular languages related to modulo counting

RAIRO - Theoretical Informatics and Applications (2008)

- 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 43.1 (2008): 95-132. <http://eudml.org/doc/92909>.

@article{Selivanov2008,

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},

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

language = {eng},

month = {1},

number = {1},

pages = {95-132},

publisher = {EDP Sciences},

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

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

volume = {43},

year = {2008},

}

TY - JOUR

AU - Selivanov, Victor L.

TI - Hierarchies and reducibilities on regular languages related to modulo counting

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/1//

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.; regular language; quantifier-alternation hierarchy; polylogtime reducibility; forbidden pattern; finite structures; complexity classes

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

ER -

## References

top- B. Borchert, On the acceptance power of regular languages. Theor. Comput. Sci.148 (1995) 207–225.
- 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.
- D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theor. Comput. Sci.104 (1992) 263–283.
- J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logic Grundl. Math.6 (1960) 66–92.
- D.A.M. Barrington, K. Compton, H. Straubing and D. Thérien, Regular languages in NC1. J. Comput. System Sci.44 (1992) 478–499.
- K. Cronauer, U. Hertrampf, H. Vollmer and K.W. Wagner, The chain method to separate counting classes. Theor. Comput. Syst.31 (1998) 93–108.
- R.S. Cohen and J.A. Brzozowski, Dot-depth of star-free events. J. Comput. System Sci.5 (1971) 1–16.
- L. Chaubard, J.-E. Pin and H. Straubing, Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci.356 (2006) 73–89.
- S. Eilenberg, Automata, Languages and Machines v. A and B. Academic Press (1974 and 1976).
- Z. Esik and M. Ito, Temporal logic with cyclic counting and the degree of aperiodicity of finite automata. Acta Cybern.16 (2003) 1–28.
- Z. Esik and K.G. Larsen, Regular languages definable by Lindström quantifiers. RAIRO-Theor. Inf. Appl.37 (2003) 179–241.
- C. Glaßer, Polylogtime-reductions decrease dot-depth, in Proc. of STACS-2005. Lect. Notes Comput. Sci.3404 (2005).
- C. Glaßer, Languages Polylog-Time Reducible to Dot-Depth 1/2. J. Comput. System Sci.73 (2007) 36–56.
- C. Glaßer and H. Schmitz, The Boolean Structure of Dot-Depth One. J. Autom. Lang. Comb.6 (2001) 437–452.
- T. Gundermann and G. Wechsung, Counting classes of finite accepting types. Computers and Artificial Intelligence6 (1987) 395–409.
- T. Gundermann, N.A. Nasser and G. Wechsung, A survey on counting classes, in Proc. of Structures in Complexity Theory (1990) 140–153.
- 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.
- A.S. Kechris, Classical Descriptive Set Theory. Springer, New York (1994).
- R. McNaughton, Algebraic decision procedures for local testability. Math. Syst. Theor.8 (1974) 60–76.
- R. McNaughton and S. Papert, Counter-Free Automata. MIT Press, Cambridge, Massachussets (1971).
- J.-E. Pin, Varieties of Formal Languages. North Oxford Academic (1986).
- 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.
- D. Perrin and J.-E. Pin, First-order logic and star-free sets. J. Comput. System Sci.32 (1986) 393–496.
- J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theor. Comput. Syst.30 (1997) 383–422.
- M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control8 (1965) 190–194.
- 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.
- V.L. Selivanov, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO-Theor. Inf. Appl.36 (2002) 29–42.
- V.L. Selivanov, Some hierarchies and reducibilities on regular languages. University of Würzburg, Technical Report 349 (2004).
- V.L. Selivanov, Some reducibilities on regular sets, in Proc. of CIE-2005. Lect. Notes Comput. Sci.3526 (2005) 430–440.
- 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.
- J. Shoenfield, Mathematical Logic. Addison Wesley, Massachussets (1967).
- A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems, Novosibirsk161 (1998) 141–155 (in Russian).
- 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.
- J. Stern, Characterizations of some classes of regular events. Theor. Comput. Sci.35 (1985) 163–176.
- H. Straubing, Finite automata, formal logic and circuit complexity. Birkhäuser, Boston (1994).
- H. Straubing, On logical description of regular languages, in Proc. of LATIN-2002. Lect. Notes Comput. Sci.2286 (2002) 528–538.
- H. Straubing, D. Thérien and W. Thomas, Regular languages defined with generalized quantifiers. Inform. Comput.118 (1995) 289–301.
- 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.
- V.L. Selivanov and K.W. Wagner, A reducibility for the dot-depth hierarchy. Theor. Comput. Sci.345 (2005) 448–472.
- W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci.25 (1982) 360–376.
- W. Thomas, An application of the Ehrenteucht-Fraïssé game in formal language theory. Mém. Soc. Math. France Ser. 216 (1984) 11–21.
- B.A. Trakhtenbrot, Synthesis of logic networks whose operators are described by means of single-placed predicate calculus. Doklady Akad. Nauk SSSR118 (1958) 646–649.
- N.K. Vereshchagin, Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk57 (1993) 51–90 (in Russian).
- K.W. Wagner, On ω-regular sets. Inform. Control43 (1979) 123–177.
- K.W. Wagner, Leaf language classes. MCU-2004. Lect. Notes Comput. Sci.3354 (2005) 60–81.
- T. Wilke, Classifying discrete temporal properties, in Proc. STACS-99. Lect. Notes Comput. Sci.1563 (1999) 32–46.

## NotesEmbed ?

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