Voir la notice de l'article provenant de la source Numdam
We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret. Comput. Sci. 262 (2001) 1-24)].
@article{ITA_2006__40_3_501_0,
author = {Jir\'askov\'a, Galina},
title = {Note on the complexity of {Las} {Vegas} automata problems},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {501--510},
publisher = {EDP-Sciences},
volume = {40},
number = {3},
year = {2006},
doi = {10.1051/ita:2006033},
mrnumber = {2269207},
zbl = {1110.68051},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2006033/}
}
TY - JOUR AU - Jirásková, Galina TI - Note on the complexity of Las Vegas automata problems JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 501 EP - 510 VL - 40 IS - 3 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2006033/ DO - 10.1051/ita:2006033 LA - en ID - ITA_2006__40_3_501_0 ER -
%0 Journal Article %A Jirásková, Galina %T Note on the complexity of Las Vegas automata problems %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 501-510 %V 40 %N 3 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2006033/ %R 10.1051/ita:2006033 %G en %F ITA_2006__40_3_501_0
Jirásková, Galina. Note on the complexity of Las Vegas automata problems. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 501-510. doi: 10.1051/ita:2006033
Cité par Sources :