Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

Victor L. Selivanov

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 36.1 (2010): 29-42. <http://eudml.org/doc/92689>.

@article{Selivanov2010,
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},
keywords = {automata theory; complexity theory; leaf-languages; Straubing hierarchy; Brzozowski hierarchy; typed Boolean hierarchy; fine hierarchy; polynomial-time hierarchy},
language = {eng},
month = {3},
number = {1},
pages = {29-42},
publisher = {EDP Sciences},
title = {Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies},
url = {http://eudml.org/doc/92689},
volume = {36},
year = {2010},
}

TY - JOUR
AU - Selivanov, Victor L.
TI - Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/3//
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/92689
ER -

References

top
  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).  
  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).  
  3. B. Borchert, On the acceptance power of regular languages. Theoret. Comput. Sci.148 (1995) 207-225.  
  4. B. Borchert, D. Kuske and F. Stephan, On existentially first-order definable languages and their relation to NP. RAIRO: Theoret. Informatics Appl.33 (1999) 259-269.  
  5. D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci.104 (1992) 263-283.  
  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.  
  7. H.-J. Burtschick and H. Vollmer, Lindström Quatifiers and Leaf Language Definability. Int. J. Found. Comput. Sci.9 (1998) 277-294.  
  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. 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.  
  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. U. Hertrampf, H. Vollmer and K.W. Wagner, On balanced vs. unbalanced computation trees. Math. Systems Theory29 (1996) 411-421.  
  12. B. Jenner, P. McKenzie and D. Therien, Logspace and logtime leaf languages. Inform. and Comput.129 (1996) 21-33.  
  13. K. Kuratowski and A. Mostowski, Set Theory. North Holland (1967).  
  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. R. McNaughton and S. Papert, Counter-free automata. MIT Press, Cambridge,Massachusets (1971).  
  16. D. Perrin and J.-E. Pin, First order logic and star-free sets. J. Comput. Systems Sci.32 (1986) 393-406.  
  17. J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Computing Systems30 (1997) 383-422.  
  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.  
  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.  
  20. V.L. Selivanov, Refining the polynomial hierarchy, Preprint No. 9. The University of Heidelberg, Chair of Mathematical Logic (1994) 20 p.  
  21. V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic60 (1995) 289-317.  
  22. V.L. Selivanov, Refining the polynomial hierarchy. Algebra and Logic38 (1999) 456-475 (Russian, there is an English translation).  
  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  
  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. A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems161 (1998) 141-155 (in Russian).  
  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. W. Thomas, Classifying regular events in symbolic logic. J. Comput. Systems Sci.25 (1982) 360-376.  
  28. N.K. Vereshchagin, Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk57 (1993) 51-90 (in Russian).  
  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.  

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.