Relating automata-theoretic hierarchies to complexity-theoretic hierarchies

Victor L. Selivanov

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

  • Volume: 36, Issue: 1, page 29-42
  • ISSN: 0988-3754

Abstract

top
We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.

How to cite

top

Selivanov, Victor L.. "Relating automata-theoretic hierarchies to complexity-theoretic hierarchies." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.1 (2002): 29-42. <http://eudml.org/doc/245018>.

@article{Selivanov2002,
abstract = {We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.},
author = {Selivanov, Victor L.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {automata theory; complexity theory; leaf-languages; Straubing hierarchy; Brzozowski hierarchy; typed Boolean hierarchy; fine hierarchy; polynomial-time hierarchy},
language = {eng},
number = {1},
pages = {29-42},
publisher = {EDP-Sciences},
title = {Relating automata-theoretic hierarchies to complexity-theoretic hierarchies},
url = {http://eudml.org/doc/245018},
volume = {36},
year = {2002},
}

TY - JOUR
AU - Selivanov, Victor L.
TI - Relating automata-theoretic hierarchies to complexity-theoretic hierarchies
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2002
PB - EDP-Sciences
VL - 36
IS - 1
SP - 29
EP - 42
AB - We show that some natural refinements of the Straubing and Brzozowski hierarchies correspond (via the so called leaf-languages) step by step to similar refinements of the polynomial-time hierarchy. This extends a result of Burtschik and Vollmer on relationship between the Straubing and the polynomial hierarchies. In particular, this applies to the Boolean hierarchy and the plus-hierarchy.
LA - eng
KW - automata theory; complexity theory; leaf-languages; Straubing hierarchy; Brzozowski hierarchy; typed Boolean hierarchy; fine hierarchy; polynomial-time hierarchy
UR - http://eudml.org/doc/245018
ER -

References

top
  1. [1] J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity I, Vol. 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag (1988). Zbl0638.68040MR1047862
  2. [2] J.L. Balcázar, J. Díaz and J. Gabarró, Structural Complexity II, Vol. 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag (1990). Zbl0746.68032MR1056474
  3. [3] B. Borchert, On the acceptance power of regular languages. Theoret. Comput. Sci. 148 (1995) 207-225. Zbl0873.68121MR1355587
  4. [4] B. Borchert, D. Kuske and F. Stephan, On existentially first-order definable languages and their relation to N P . RAIRO: Theoret. Informatics Appl. 33 (1999) 259-269. Zbl0949.03035MR1728426
  5. [5] D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. Zbl0754.68049MR1186181
  6. [6] J.A. Brzozowski and R Knast, The dot-depth hierarchy of star-free languages is infinite. J. Comput. Systems Sci. 16 (1978) 37-55. Zbl0368.68074MR471451
  7. [7] H.-J. Burtschick and H. Vollmer, Lindström Quatifiers and Leaf Language Definability. Int. J. Found. Comput. Sci. 9 (1998) 277-294. Zbl1319.68104
  8. [8] E. Hemaspaandra, L. Hemaspaandra and H. Hempel, What’s up with downward collapse: Using the easy-hard technique to link Boolean and polynomial hierarchy collapses. Compl. Theory Column 21, ACM-SIGACT Newslett. 29 (1998) 10-22. 
  9. [9] U. Hertrampf, C. Lautemann, T. Schwentick, H. Vollmer and K.W. Wagner, On the power of polynomial time bit-reductions, in Proc. 8th Structure in Complexity Theory (1993) 200-207. MR1310801
  10. [10] U. Hertrampf, H. Vollmer and K.W. Wagner, On the power of number-theoretic operations with respect to counting, in Proc. 10th Structure in Complexity Theory (1995) 299-314. 
  11. [11] U. Hertrampf, H. Vollmer and K.W. Wagner, On balanced vs. unbalanced computation trees. Math. Systems Theory 29 (1996) 411-421. Zbl0853.68097MR1389468
  12. [12] B. Jenner, P. McKenzie and D. Therien, Logspace and logtime leaf languages. Inform. and Comput. 129 (1996) 21-33. Zbl0864.68057MR1408830
  13. [13] K. Kuratowski and A. Mostowski, Set Theory. North Holland (1967). Zbl0165.01701MR229526
  14. [14] J. Köbler, U. Shöning and K.W. Wagner, The difference and truth-table hierarchies for NP. Dep. of Informatics, Koblenz, Preprint 7 (1986). 
  15. [15] R. McNaughton and S. Papert, Counter-free automata. MIT Press, Cambridge, Massachusets (1971). Zbl0232.94024MR371538
  16. [16] D. Perrin and J.-E. Pin, First order logic and star-free sets. J. Comput. Systems Sci. 32 (1986) 393-406. Zbl0618.03015MR858236
  17. [17] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Computing Systems 30 (1997) 383-422. Zbl0872.68119MR1450862
  18. [18] S. Reith and K.W. Wagner, On Boolean lowness and Boolean highness, in Proc. 4-th Ann. Int. Computing and Combinatorics Conf. Springer, Berlin, Lecture Notes in Comput. Sci. 1449 (1998) 147-156. Zbl0912.68049MR1683382
  19. [19] V.L. Selivanov, Two refinements of the polynomial hierarchy, in Proc. of Symposium on Theor. Aspects of Computer Science STACS-94. Springer, Berlin, Lecture Notes in Comput. Sci. 775 (1994) 439-448. Zbl0941.03544MR1288556
  20. [20] V.L. Selivanov, Refining the polynomial hierarchy, Preprint No. 9. The University of Heidelberg, Chair of Mathematical Logic (1994) 20 p. MR1763384
  21. [21] V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic 60 (1995) 289-317. Zbl0824.03022MR1324514
  22. [22] V.L. Selivanov, Refining the polynomial hierarchy. Algebra and Logic 38 (1999) 456-475 (Russian, there is an English translation). Zbl0932.03052MR1763384
  23. [23] V.L. Selivanov, A logical approach to decidability of hierarchies of regular star-free languages, in Proc. of 18-th Int. Symposium on Theor. Aspects of Computer Science STACS-2001 in Dresden, Germany. Springer, Berlin, Lecture Notes in Comput. Sci. 2010 (2001) 539-550 Zbl0976.03042MR1892340
  24. [24] 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 p. 
  25. [25] A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems 161 (1998) 141-155 (in Russian). Zbl0932.03053MR1778013
  26. [26] H. Schmitz and K.W. Wagner, The Boolean hierarchy over level 1/2 of the Straubing–Therien hierarchy, Technical Report 201. Inst. für Informatik, Univ. Würzburg available at http://www.informatik.uni-wuerzburg.de. 
  27. [27] W. Thomas, Classifying regular events in symbolic logic. J. Comput. Systems Sci. 25 (1982) 360-376. Zbl0503.68055MR684265
  28. [28] 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
  29. [29] G. Wechsung and K. Wagner, On the Boolean closure of NP, in Proc. of the 1985 Int. Conf. on Fundamentals of Computation theory. Springer-Verlag, Lecture Notes in Comput. Sci. 199 (1985) 485-493. Zbl0581.68043MR821265

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.