Note on the complexity of Las Vegas automata problems

Galina Jirásková

RAIRO - Theoretical Informatics and Applications (2006)

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

Abstract

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

How to cite

top

Jirá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
  1. S. Cho and D.T. Huynh, The parallel complexity of finite-state automata problems. Inform. Comput.97 (1992) 1–22.  
  2. M. Hirvensalo and S. Seibert, Lower bounds for Las Vegas automata by information theory. RAIRO-Inf. Theor. Appl.37 (2003) 39–49.  
  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.  
  5. J. Hromkovič and G. Schnitger, On the power of Las Vegas II. Two-way finite automata. Theoret. Comput. Sci.262 (2001) 1–24.  
  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.  
  7. N. Immerman, Nondeterministic space is closed under complement. SIAM J. Comput.17 (1988) 935–938.  
  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.  
  9. T. Jiang and B. Ravikumar, Minimal NFA problems are hard. SIAM J. Comput.22 (1993) 1117–1141.  
  10. N.D. Jones, Space-bounded reducibility among combinatorial problems. J. Comput. Syst. Sci.11 (1975) 68–85.  
  11. N.D. Jones, Y.E. Lien and W.T. Laaser, New problems complete for nondeterministic log space. Math. Syst. Theory10 (1976) 1–17.  
  12. O.B. Lupanov, A comparison of two types of finite automata. Problemy Kibernetiki9 (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.  
  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.  
  17. R. Szelepscényi, The method of forced enumeration for nondeterministic automata. Acta Inform.29 (1988) 279–284.  
  18. W.G. Tzeng, A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput.21 (1992) 216–227.  
  19. W.G. Tzeng, On path equivalence of nondeterministic finite automata. Inform. Process. Lett.58 (1996) 43–46.  

NotesEmbed ?

top

You must be logged in to post comments.