Hierarchies and reducibilities on regular languages related to modulo counting

Victor L. Selivanov

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

  • 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 - 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. [1] B. Borchert, On the acceptance power of regular languages. Theor. Comput. Sci. 148 (1995) 207–225. Zbl0873.68121MR1355587
  2. [2] B. Borchert, D. Kuske and F. Stephan, On existentially first-order definable languages and their relation to N P . RAIRO-Theor. Inf. Appl. 33 (1999) 259–269. Zbl0949.03035MR1728426
  3. [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. [4] J.R. Büchi, Weak second-order arithmetic and finite automata. Z. Math. Logic Grundl. Math. 6 (1960) 66–92. Zbl0103.24705MR125010
  5. [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. [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. [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. [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. [9] S. Eilenberg, Automata, Languages and Machines v. A and B. Academic Press (1974 and 1976). Zbl0317.94045
  10. [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. [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. [12] C. Glaßer, Polylogtime-reductions decrease dot-depth, in Proc. of STACS-2005. Lect. Notes Comput. Sci. 3404 (2005). Zbl1118.68523
  13. [13] C. Glaßer, Languages Polylog-Time Reducible to Dot-Depth 1/2. J. Comput. System Sci. 73 (2007) 36–56. Zbl1178.68315MR2279030
  14. [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. [15] T. Gundermann and G. Wechsung, Counting classes of finite accepting types. Computers and Artificial Intelligence 6 (1987) 395–409. Zbl0638.68027MR974644
  16. [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. [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. [18] A.S. Kechris, Classical Descriptive Set Theory. Springer, New York (1994). Zbl0819.04002MR1321597
  19. [19] R. McNaughton, Algebraic decision procedures for local testability. Math. Syst. Theor. 8 (1974) 60–76. Zbl0287.02022MR392544
  20. [20] R. McNaughton and S. Papert, Counter-Free Automata. MIT Press, Cambridge, Massachussets (1971). Zbl0232.94024MR371538
  21. [21] J.-E. Pin, Varieties of Formal Languages. North Oxford Academic (1986). Zbl0655.68095MR912694
  22. [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. [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. [24] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theor. Comput. Syst. 30 (1997) 383–422. Zbl0872.68119MR1450862
  25. [25] M.P. Schützenberger, On finite monoids having only trivial subgroups. Inform. Control 8 (1965) 190–194. Zbl0131.02001MR176883
  26. [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. [27] V.L. Selivanov, Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO-Theor. Inf. Appl. 36 (2002) 29–42. Zbl1029.03027MR1928157
  28. [28] V.L. Selivanov, Some hierarchies and reducibilities on regular languages. University of Würzburg, Technical Report 349 (2004). 
  29. [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. [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. Zbl1155.03310MR2380448
  31. [31] J. Shoenfield, Mathematical Logic. Addison Wesley, Massachussets (1967). Zbl0155.01102MR225631
  32. [32] A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems, Novosibirsk 161 (1998) 141–155 (in Russian). Zbl0932.03053MR1778013
  33. [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. [34] J. Stern, Characterizations of some classes of regular events. Theor. Comput. Sci. 35 (1985) 163–176. Zbl0604.68066MR785905
  35. [35] H. Straubing, Finite automata, formal logic and circuit complexity. Birkhäuser, Boston (1994). Zbl0816.68086MR1269544
  36. [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. [37] H. Straubing, D. Thérien and W. Thomas, Regular languages defined with generalized quantifiers. Inform. Comput. 118 (1995) 289–301. Zbl0826.68072MR1331729
  38. [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. [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. [40] W. Thomas, Classifying regular events in symbolic logic. J. Comput. System Sci. 25 (1982) 360–376. Zbl0503.68055MR684265
  41. [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. [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. [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. [44] K.W. Wagner, On ω -regular sets. Inform. Control 43 (1979) 123–177. Zbl0434.68061MR553694
  45. [45] K.W. Wagner, Leaf language classes. MCU-2004. Lect. Notes Comput. Sci. 3354 (2005) 60–81. Zbl1119.68091MR2178402
  46. [46] T. Wilke, Classifying discrete temporal properties, in Proc. STACS-99. Lect. Notes Comput. Sci. 1563 (1999) 32–46. Zbl0926.03018MR1734035

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.