Voir la notice de l'article provenant de la source Numdam
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://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
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
Cité par Sources :