# Note on the complexity of Las Vegas automata problems

RAIRO - Theoretical Informatics and Applications (2006)

- Volume: 40, Issue: 3, page 501-510
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topJirásková, Galina. "Note on the complexity of Las Vegas automata problems." RAIRO - Theoretical Informatics and Applications 40.3 (2006): 501-510. <http://eudml.org/doc/249701>.

@article{Jirásková2006,

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

author = {Jirásková, Galina},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Las Vegas finite automata; deterministic and nondeterministic finite automata; computational complexity.; computational complexity},

language = {eng},

month = {10},

number = {3},

pages = {501-510},

publisher = {EDP Sciences},

title = {Note on the complexity of Las Vegas automata problems},

url = {http://eudml.org/doc/249701},

volume = {40},

year = {2006},

}

TY - JOUR

AU - Jirásková, Galina

TI - Note on the complexity of Las Vegas automata problems

JO - RAIRO - Theoretical Informatics and Applications

DA - 2006/10//

PB - EDP Sciences

VL - 40

IS - 3

SP - 501

EP - 510

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

LA - eng

KW - Las Vegas finite automata; deterministic and nondeterministic finite automata; computational complexity.; computational complexity

UR - http://eudml.org/doc/249701

ER -

## References

top- S. Cho and D.T. Huynh, The parallel complexity of finite-state automata problems. Inform. Comput.97 (1992) 1–22. Zbl0755.68051
- M. Hirvensalo and S. Seibert, Lower bounds for Las Vegas automata by information theory. RAIRO-Inf. Theor. Appl.37 (2003) 39–49. Zbl1084.68061
- 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.
- 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. Zbl1007.68065
- J. Hromkovič and G. Schnitger, On the power of Las Vegas II. Two-way finite automata. Theoret. Comput. Sci.262 (2001) 1–24. Zbl0983.68098
- 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. Zbl0334.68044
- N. Immerman, Nondeterministic space is closed under complement. SIAM J. Comput.17 (1988) 935–938. Zbl0668.68056
- 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. Zbl0741.68078
- T. Jiang and B. Ravikumar, Minimal NFA problems are hard. SIAM J. Comput.22 (1993) 1117–1141. Zbl0799.68079
- N.D. Jones, Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci.11 (1975) 68–85. Zbl0317.02039
- N.D. Jones, Y.E. Lien and W.T. Laaser, New problems complete for nondeterministic log space. Math. Syst. Theory10 (1976) 1–17. Zbl0341.68035
- O.B. Lupanov, A comparison of two types of finite automata. Problemy Kibernetiki9 (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.
- 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. Zbl0229.94033
- M. Sipser, Introduction to the Theory of Computation. PWS Publishing Company, Boston (1997). Zbl1169.68300
- 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. Zbl0359.68050
- R. Szelepscényi, The method of forced enumeration for nondeterministic automata. Acta Inform.29 (1988) 279–284.
- W.G. Tzeng, A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput.21 (1992) 216–227. Zbl0755.68075
- W.G. Tzeng, On path equivalence of nondeterministic finite automata. Inform. Process. Lett.58 (1996) 43–46. Zbl0875.68650

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.