Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov

RAIRO - Theoretical Informatics and Applications (2008)

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

Abstract

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

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.