zbMATH — the first resource for mathematics

Unary finite automata vs. arithmetic progressions. (English) Zbl 1202.68241
Summary: We point out a subtle error in the proof of Chrobak’s theorem that every unary NFA can be represented as a union of arithmetic progressions that is at most quadratically large. We propose a correction for this and show how Martinez’s polynomial time algorithm, which realizes Chrobak’s theorem, can be made correct accordingly. We also show that Martinez’s algorithm cannot be improved to have logarithmic space, unless L = NL.

68Q45 Formal languages and automata
Full Text: DOI
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley · Zbl 0286.68029
[2] T. Anderson, N. Rampersad, N. Santean, J. Shallit, Finite automata, palindromes, powers, and patters, in: LATA 2008, pp. 52-63 · Zbl 1156.68441
[3] Brauer, A., On a problem of partitions, Amer. J. math., 64, 299-312, (1942) · Zbl 0061.06801
[4] Chrobak, M., Finite automata and unary languages, Theoret. comput. sci., Theoret. comput. sci., 302, 497-498, (2003), Errata
[5] H. Gruber, M. Holzer, Computational complexity of NFA minimization for finite and unary languages, in: LATA 2008, pp. 261-272
[6] Kozen, D., Automata and computability, (1997), Springer-Verlag · Zbl 0883.68055
[7] Litow, B., A special case of a unary regular language containment, Theory comput. syst., 39, 743-751, (2006) · Zbl 1100.68053
[8] Liubicz, U.I., Bounds for the optimal determinization of nondeterministic autonomic automata, Sibirskii matemat. journal, 2, 337-355, (1964), (in Russian)
[9] A. Martinez, Efficient computation of regular expressions from unary NFAs, in: DFCS 2002, pp. 174-187
[10] A. Martinez, Topics in formal languages: String enumeration, unary NFAs and state complexity. Master thesis, Faculty of Mathematics, Univ. of Waterloo, 2002
[11] J. Shallit, The Frobenius problem and its generalization, in: DLT 2008, pp. 72-83 · Zbl 1161.11319
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.