Voir la notice de l'article provenant de la source Numdam
We introduce the notion of nested distance desert automata as a joint generalization of distance automata and desert automata. We show that limitedness of nested distance desert automata is PSPACE-complete. As an application, we show that it is decidable in space whether the language accepted by an -state non-deterministic automaton is of a star height less than a given integer (concerning rational expressions with union, concatenation and iteration), which is the first ever complexity bound for the star height problem.
@article{ITA_2005__39_3_455_0,
author = {Kirsten, Daniel},
title = {Distance desert automata and the star height problem},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {455--509},
publisher = {EDP-Sciences},
volume = {39},
number = {3},
year = {2005},
doi = {10.1051/ita:2005027},
mrnumber = {2157045},
zbl = {1082.20041},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2005027/}
}
TY - JOUR AU - Kirsten, Daniel TI - Distance desert automata and the star height problem JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2005 SP - 455 EP - 509 VL - 39 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2005027/ DO - 10.1051/ita:2005027 LA - en ID - ITA_2005__39_3_455_0 ER -
%0 Journal Article %A Kirsten, Daniel %T Distance desert automata and the star height problem %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2005 %P 455-509 %V 39 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2005027/ %R 10.1051/ita:2005027 %G en %F ITA_2005__39_3_455_0
Kirsten, Daniel. Distance desert automata and the star height problem. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 3, pp. 455-509. doi: 10.1051/ita:2005027
Cité par Sources :