×

zbMATH — the first resource for mathematics

Note on the complexity of Las Vegas automata problems. (English) Zbl 1110.68051
Summary: 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 J. Hromkovič and G. Schnitger [Theor. Comput. Sci. 262, No. 1–2, 1–24 (2001; Zbl 0983.68098)].
MSC:
68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q45 Formal languages and automata
Citations:
Zbl 0983.68098
PDF BibTeX XML Cite
Full Text: DOI Numdam EuDML Link
References:
[1] S. Cho and D.T. Huynh , The parallel complexity of finite-state automata problems . Inform. Comput. 97 ( 1992 ) 1 - 22 . Zbl 0755.68051 · 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 · Zbl 1084.68061
[3] J.E. Hopcroft , An \( n \log n \) 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 · 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 · 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 · Zbl 0334.68044
[7] N. Immerman , Nondeterministic space is closed under complement . SIAM J. Comput. 17 ( 1988 ) 935 - 938 . Zbl 0668.68056 · 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 · Zbl 0741.68078
[9] T. Jiang and B. Ravikumar , Minimal NFA problems are hard . SIAM J. Comput. 22 ( 1993 ) 1117 - 1141 . Zbl 0799.68079 · Zbl 0799.68079
[10] N.D. Jones , Space-bounded reducibility among combinatorial problems . J. Comput. Syst. Sci. 11 ( 1975 ) 68 - 85 . Zbl 0317.02039 · 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 · 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 · Zbl 0229.94033
[15] M. Sipser , Introduction to the Theory of Computation . PWS Publishing Company, Boston ( 1997 ). · Zbl 1169.68300
[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 · Zbl 0359.68050
[17] R. Szelepscényi , The method of forced enumeration for nondeterministic automata . Acta Inform. 29 ( 1988 ) 279 - 284 . Zbl 0638.68046 · 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 · Zbl 0755.68075
[19] W.G. Tzeng , On path equivalence of nondeterministic finite automata . Inform. Process. Lett. 58 ( 1996 ) 43 - 46 . Zbl 0875.68650 · Zbl 0875.68650
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.