Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-29T06:03:04.703Z Has data issue: false hasContentIssue false
  • English
  • Français

Note on the complexity of Las Vegas automata problems

Published online by Cambridge University Press:  18 October 2006

Galina Jirásková
Galina Jirásková*
Affiliation:
Mathematical Institute, Slovak Academy of Sciences, Grešákova 6, 040 01 Košice, Slovakia; [email protected]
Get access

Abstract

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

Keywords

Las Vegas finite automatadeterministic and nondeterministic finite automatacomputational complexity.
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 40 , Issue 3: Word Avoidability Complexity And Morphisms (WACAM) , July 2006 , pp. 501 - 510
Copyright
© EDP Sciences, 2006

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Cho, S. and Huynh, D.T., The parallel complexity of finite-state automata problems. Inform. Comput. 97 (1992) 1–22. CrossRef
Hirvensalo, M. and Seibert, S., Lower bounds for Las Vegas automata by information theory. RAIRO-Inf. Theor. Appl. 37 (2003) 39–49. CrossRef
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.
Hromkovič, J. and Schnitger, G., On the power of Las Vegas for one-way communication complexity, OBDDs, and finite automata. Inform. Comput. 169 (2001) 284–296. CrossRef
Hromkovič, J. and Schnitger, G., On the power of Las Vegas II. Two-way finite automata. Theoret. Comput. Sci. 262 (2001) 1–24. CrossRef
Hunt, H.B., Rozenkrantz, D.J. and Szymanski, T.G., On the equivalence, containment, and covering problems for the regular and context-free languages. J. Comput. Syst. Sci. 12 (1976) 222–268. CrossRef
Immerman, N., Nondeterministic space is closed under complement. SIAM J. Comput. 17 (1988) 935–938. CrossRef
Jiang, T. and Ravikumar, B., A note on the space complexity of some decision problems for finite automata. Inform. Process. Lett. 40 (1991) 25–31. CrossRef
Jiang, T. and Ravikumar, B., Minimal NFA problems are hard. SIAM J. Comput. 22 (1993) 1117–1141. CrossRef
Jones, N.D., Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci. 11 (1975) 68–85. CrossRef
Jones, N.D., Lien, Y.E. and Laaser, W.T., New problems complete for nondeterministic log space. Math. Syst. Theory 10 (1976) 1–17. CrossRef
Lupanov, O.B., A comparison of two types of finite automata. Problemy Kibernetiki 9 (1963) 321–326 (in Russian).
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.
Moore, F.R., 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. CrossRef
M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997).
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.
Szelepscényi, R., The method of forced enumeration for nondeterministic automata. Acta Inform. 29 (1988) 279–284. CrossRef
Tzeng, W.G., A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. 21 (1992) 216–227. CrossRef
Tzeng, W.G., On path equivalence of nondeterministic finite automata. Inform. Process. Lett. 58 (1996) 43–46.