# Relating Automata-theoretic Hierarchies to Complexity-theoretic Hierarchies

RAIRO - Theoretical Informatics and Applications (2010)

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

## Access Full Article

top## Abstract

top## How to cite

topSelivanov, 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- 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).
- 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).
- B. Borchert, On the acceptance power of regular languages. Theoret. Comput. Sci.148 (1995) 207-225. Zbl0873.68121
- 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. Zbl0949.03035
- D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci.104 (1992) 263-283. Zbl0754.68049
- 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.68074
- H.-J. Burtschick and H. Vollmer, Lindström Quatifiers and Leaf Language Definability. Int. J. Found. Comput. Sci.9 (1998) 277-294. Zbl1319.68104
- 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.
- 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.
- 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.
- U. Hertrampf, H. Vollmer and K.W. Wagner, On balanced vs. unbalanced computation trees. Math. Systems Theory29 (1996) 411-421. Zbl0853.68097
- B. Jenner, P. McKenzie and D. Therien, Logspace and logtime leaf languages. Inform. and Comput.129 (1996) 21-33. Zbl0864.68057
- K. Kuratowski and A. Mostowski, Set Theory. North Holland (1967).
- 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).
- R. McNaughton and S. Papert, Counter-free automata. MIT Press, Cambridge,Massachusets (1971). Zbl0232.94024
- D. Perrin and J.-E. Pin, First order logic and star-free sets. J. Comput. Systems Sci.32 (1986) 393-406. Zbl0618.03015
- J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Computing Systems30 (1997) 383-422. Zbl0872.68119
- 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.68049
- 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.03544
- V.L. Selivanov, Refining the polynomial hierarchy, Preprint No. 9. The University of Heidelberg, Chair of Mathematical Logic (1994) 20 p.
- V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic60 (1995) 289-317. Zbl0824.03022
- V.L. Selivanov, Refining the polynomial hierarchy. Algebra and Logic38 (1999) 456-475 (Russian, there is an English translation). Zbl0932.03052
- 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.03042
- 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.
- A.G. Shukin, Difference hierarchies of regular languages. Comput. Systems161 (1998) 141-155 (in Russian).
- 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.
- W. Thomas, Classifying regular events in symbolic logic. J. Comput. Systems Sci.25 (1982) 360-376. Zbl0503.68055
- N.K. Vereshchagin, Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk57 (1993) 51-90 (in Russian). Zbl0822.68035
- 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.