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.

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)].

DOI : 10.1051/ita:2006033
Classification : 68Q19, 68Q17
Mots-clés : Las Vegas finite automata, deterministic and nondeterministic finite automata, computational complexity 
@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://www.numdam.org/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://www.numdam.org/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://www.numdam.org/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. http://www.numdam.org/articles/10.1051/ita:2006033/

[1] S. Cho and D.T. Huynh, The parallel complexity of finite-state automata problems. Inform. Comput. 97 (1992) 1-22. | Zbl

[2] M. Hirvensalo and S. Seibert, Lower bounds for Las Vegas automata by information theory. RAIRO-Inf. Theor. Appl. 37 (2003) 39-49. | Numdam | Zbl

[3] J.E. Hopcroft, An nlogn algorithm for minimizing the states in a finite automaton, in The Theory of Machines and Computations, edited by Z. Kohavi. Academic Press, New York (1971) 171-179.

[4] J. Hromkovič and G. Schnitger, On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inform. Comput. 169 (2001) 284-296. | Zbl

[5] J. Hromkovič and G. Schnitger, On the power of Las Vegas II. Two-way finite automata. Theoret. Comput. Sci. 262 (2001) 1-24. | Zbl

[6] H.B. Hunt, D.J. Rozenkrantz and T.G. Szymanski, On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci. 12 (1976) 222-268. | Zbl

[7] N. Immerman, Nondeterministic space is closed under complement. SIAM J. Comput. 17 (1988) 935-938. | Zbl

[8] T. Jiang and B. Ravikumar, A note on the space complexity of some decision problems for finite automata. Inform. Process. Lett. 40 (1991) 25-31. | Zbl

[9] T. Jiang and B. Ravikumar, Minimal NFA problems are hard. SIAM J. Comput. 22 (1993) 1117-1141. | Zbl

[10] N.D. Jones, Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11 (1975) 68-85. | Zbl

[11] N.D. Jones, Y.E. Lien and W.T. Laaser, New problems complete for nondeterministic log space. Math. Syst. Theory 10 (1976) 1-17. | Zbl

[12] O.B. Lupanov, A comparison of two types of finite automata. Problemy Kibernetiki 9 (1963) 321-326 (in Russian).

[13] A.R. Meyer and M.J. Fischer, Economy of description by automata, grammars and formal systems, in Proc. 12th Annual Symposium on Switching and Automata Theory (1971) 188-191.

[14] F.R. Moore, On the bounds for state-set size in the proofs of equivalence between deterministic, nondeterministic, and two-way finite automata. IEEE Trans. Comput. 20 (1971) 1211-1214. | Zbl

[15] M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997).

[16] L.J. Stockmeyer and A.R. Meyer, Word problems requiring exponential time, in Proc. 5th Annual ACM Symp. on the Theory of Computing (1973) 1-9. | Zbl

[17] R. Szelepscényi, The method of forced enumeration for nondeterministic automata. Acta Inform. 29 (1988) 279-284. | Zbl

[18] W.G. Tzeng, A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21 (1992) 216-227. | Zbl

[19] W.G. Tzeng, On path equivalence of nondeterministic finite automata. Inform. Process. Lett. 58 (1996) 43-46. | Zbl

Cité par Sources :