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.
@article{ITA_2002__36_1_29_0,
author = {Selivanov, Victor L.},
title = {Relating automata-theoretic hierarchies to complexity-theoretic hierarchies},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {29--42},
publisher = {EDP-Sciences},
volume = {36},
number = {1},
year = {2002},
doi = {10.1051/ita:2002003},
mrnumber = {1928157},
zbl = {1029.03027},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita:2002003/}
}
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 SP - 29 EP - 42 VL - 36 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita:2002003/ DO - 10.1051/ita:2002003 LA - en ID - ITA_2002__36_1_29_0 ER -
%0 Journal Article %A Selivanov, Victor L. %T Relating automata-theoretic hierarchies to complexity-theoretic hierarchies %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2002 %P 29-42 %V 36 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita:2002003/ %R 10.1051/ita:2002003 %G en %F ITA_2002__36_1_29_0
Selivanov, Victor L. Relating automata-theoretic hierarchies to complexity-theoretic hierarchies. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 1, pp. 29-42. doi : 10.1051/ita:2002003. http://archive.numdam.org/articles/10.1051/ita:2002003/
[1] , and, Structural Complexity I, Vol. 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag (1988). | MR | Zbl
[2] , and, Structural Complexity II, Vol. 11 of EATCS Monographs on Theoretical Computer Science. Springer-Verlag (1990). | MR | Zbl
[3] , On the acceptance power of regular languages. Theoret. Comput. Sci. 148 (1995) 207-225. | MR | Zbl
[4] , and, On existentially first-order definable languages and their relation to . RAIRO: Theoret. Informatics Appl. 33 (1999) 259-269. | Numdam | MR | Zbl
[5] , and, A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. | MR | Zbl
[6] and R Knast, The dot-depth hierarchy of star-free languages is infinite. J. Comput. Systems Sci. 16 (1978) 37-55. | MR | Zbl
[7] and, Lindström Quatifiers and Leaf Language Definability. Int. J. Found. Comput. Sci. 9 (1998) 277-294.
[8] , and, 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] ,,, and, On the power of polynomial time bit-reductions, in Proc. 8th Structure in Complexity Theory (1993) 200-207. | MR
[10] , and, On the power of number-theoretic operations with respect to counting, in Proc. 10th Structure in Complexity Theory (1995) 299-314.
[11] , and, On balanced vs. unbalanced computation trees. Math. Systems Theory 29 (1996) 411-421. | MR | Zbl
[12] , and, Logspace and logtime leaf languages. Inform. and Comput. 129 (1996) 21-33. | MR | Zbl
[13] and, Set Theory. North Holland (1967). | MR | Zbl
[14] , and, The difference and truth-table hierarchies for NP. Dep. of Informatics, Koblenz, Preprint 7 (1986).
[15] and, Counter-free automata. MIT Press, Cambridge, Massachusets (1971). | MR | Zbl
[16] and, First order logic and star-free sets. J. Comput. Systems Sci. 32 (1986) 393-406. | MR | Zbl
[17] and, Polynomial closure and unambiguous product. Theory Computing Systems 30 (1997) 383-422. | MR | Zbl
[18] and, 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. | MR | Zbl
[19] , 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. | MR | Zbl
[20] , Refining the polynomial hierarchy, Preprint No. 9. The University of Heidelberg, Chair of Mathematical Logic (1994) 20 p. | MR
[21] , Fine hierarchies and Boolean terms. J. Symb. Logic 60 (1995) 289-317. | MR | Zbl
[22] , Refining the polynomial hierarchy. Algebra and Logic 38 (1999) 456-475 (Russian, there is an English translation). | MR | Zbl
[23] , 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 | MR | Zbl
[24] and, On hierarchies of regular star-free languages (in Russian). Preprint 69 of A.P. Ershov Institute of Informatics Systems (2000) 28 p.
[25] , Difference hierarchies of regular languages. Comput. Systems 161 (1998) 141-155 (in Russian). | MR | Zbl
[26] and, 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] , Classifying regular events in symbolic logic. J. Comput. Systems Sci. 25 (1982) 360-376. | MR | Zbl
[28] , Relativizable and non-relativizable theorems in the polynomial theory of algorithms. Izvestiya Rossiiskoi Akademii Nauk 57 (1993) 51-90 (in Russian). | MR | Zbl
[29] and, 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. | MR | Zbl
Cité par Sources :
