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.

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.

DOI : 10.1051/ita:2002003
Classification : 03D05, 03D15, 03D55 
@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 = {https://www.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  - https://www.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 https://www.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. https://www.numdam.org/articles/10.1051/ita:2002003/

[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). | MR | Zbl

[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). | MR | Zbl

[3] B. Borchert, On the acceptance power of regular languages. Theoret. Comput. Sci. 148 (1995) 207-225. | MR | Zbl

[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. | Numdam | MR | Zbl

[5] D.P. Bovet, P. Crescenzi and R. Silvestri, A uniform approach to define complexity classes. Theoret. Comput. Sci. 104 (1992) 263-283. | MR | Zbl

[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. | MR | Zbl

[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. | MR

[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 Theory 29 (1996) 411-421. | MR | Zbl

[12] B. Jenner, P. Mckenzie and D. Therien, Logspace and logtime leaf languages. Inform. and Comput. 129 (1996) 21-33. | MR | Zbl

[13] K. Kuratowski and A. Mostowski, Set Theory. North Holland (1967). | MR | Zbl

[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). | MR | Zbl

[16] D. Perrin and J.-E. Pin, First order logic and star-free sets. J. Comput. Systems Sci. 32 (1986) 393-406. | MR | Zbl

[17] J.-E. Pin and P. Weil, Polynomial closure and unambiguous product. Theory Computing Systems 30 (1997) 383-422. | MR | Zbl

[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. | MR | Zbl

[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. | MR | Zbl

[20] V.L. Selivanov, Refining the polynomial hierarchy, Preprint No. 9. The University of Heidelberg, Chair of Mathematical Logic (1994) 20 p. | MR

[21] V.L. Selivanov, Fine hierarchies and Boolean terms. J. Symb. Logic 60 (1995) 289-317. | MR | Zbl

[22] V.L. Selivanov, Refining the polynomial hierarchy. Algebra and Logic 38 (1999) 456-475 (Russian, there is an English translation). | MR | Zbl

[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 | MR | Zbl

[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. Systems 161 (1998) 141-155 (in Russian). | MR | Zbl

[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. | MR | Zbl

[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). | MR | Zbl

[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. | MR | Zbl

  • Selivanov, Victor L. Hierarchies and reducibilities on regular languages related to modulo counting, RAIRO - Theoretical Informatics and Applications, Volume 43 (2009) no. 1, p. 95 | DOI:10.1051/ita:2007063
  • SELIVANOV, VICTOR FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES, International Journal of Foundations of Computer Science, Volume 19 (2008) no. 03, p. 649 | DOI:10.1142/s0129054108005875
  • Selivanov, Victor L.; Wagner, Klaus W. Complexity of Aperiodicity for Topological Properties of Regular ω-Languages, Logic and Theory of Algorithms, Volume 5028 (2008), p. 533 | DOI:10.1007/978-3-540-69407-6_57
  • Selivanov, Victor L. Fine hierarchies and m-reducibilities in theoretical computer science, Theoretical Computer Science, Volume 405 (2008) no. 1-2, p. 116 | DOI:10.1016/j.tcs.2008.06.031
  • Selivanov, Victor L. Some Reducibilities on Regular Sets, New Computational Paradigms, Volume 3526 (2005), p. 430 | DOI:10.1007/11494645_53
  • Selivanov, Victor L.; Wagner, Klaus W. A reducibility for the dot-depth hierarchy, Theoretical Computer Science, Volume 345 (2005) no. 2-3, p. 448 | DOI:10.1016/j.tcs.2005.07.020
  • Borchert, Bernd; Lange, Klaus-Jörn; Stephan, Frank; Tesson, Pascal; Thérien, Denis The Dot-Depth and the Polynomial Hierarchy Correspond on the Delta Levels, Developments in Language Theory, Volume 3340 (2004), p. 89 | DOI:10.1007/978-3-540-30550-7_8
  • Selivanov, Victor L.; Wagner, Klaus W. A Reducibility for the Dot-Depth Hierarchy, Mathematical Foundations of Computer Science 2004, Volume 3153 (2004), p. 783 | DOI:10.1007/978-3-540-28629-5_61

Cité par 8 documents. Sources : Crossref