Geodesic
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

Voir la notice de l'article provenant de la source Numdam

DOI MR   Zbl

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 
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
@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},
     year = {2002},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {1},
     doi = {10.1051/ita:2002003},
     mrnumber = {1928157},
     zbl = {1029.03027},
     language = {en},
     url = {http://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/articles/10.1051/ita:2002003/
%R 10.1051/ita:2002003
%G en
%F ITA_2002__36_1_29_0

Cité par Sources :