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 : https://doi.org/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,
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},
zbl = {1110.68051},
mrnumber = {2269207},
language = {en},
url = {http://www.numdam.org/articles/10.1051/ita:2006033/}
}
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 0755.68051

[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 1084.68061

[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 1007.68065

[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 0983.68098

[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 0334.68044

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

[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 0741.68078

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

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

[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 0341.68035

[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 0229.94033

[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 0359.68050

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

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

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