×

zbMATH — the first resource for mathematics

Finite automata and unary languages. (English) Zbl 0638.68096
Summary: We prove that \(O(e^{\sqrt{n \log n}})\) states are sufficient to simulate an n-state nondeterministic finite automaton recognizing a unary language by a one-way deterministic finite automata. The lower bound is the same. Similar tight bounds are shown for the simulation of a two-way deterministic finite automata by a one-way deterministic finite automata and a one-way nondeterministic finite automaton. We also show that O(n 2) states are sufficient and necessary to simulate an n-state one-way nondeterministic finite automaton recognizing a unary language by a two- way deterministic finite automata.

MSC:
68Q45 Formal languages and automata
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Barnes, B., A two-way automaton with fewer states than any equivalent one-way automaton, IEEE trans. on comp., C-20, 4, 474-475, (1974) · Zbl 0218.02032
[2] Berman, P.; Lingas, A., On the complexity of regular languages in terms of finite automata, () · Zbl 0364.68057
[3] Brauer, A., On a problem of partitions, Amer. J. math., 64, 299-312, (1942) · Zbl 0061.06801
[4] Brauer, A.; Shockley, J.E., On a problem of Frobenius, J. reine angew. math., 211, 215-220, (1962) · Zbl 0108.04604
[5] Chandra, A.K.; Kozen, D.C.; Stockmeyer, L.J., Alternation, J. assoc. comput. Mach., 28, 114-133, (1981) · Zbl 0473.68043
[6] Erdös, P.; Graham, R.L., On a linear Diophantine problem of Frobenius, Acta arithm., 21, 399-408, (1972) · Zbl 0246.10010
[7] Ershov, U.L., On a conjecture of W.U. uspenskii, (), 45-48, (in Russian)
[8] Friedman, A.R.; Ladner, R.E., Space bounds for processing contentless inputs, J. comput. system sci., 11, 118-128, (1975) · Zbl 0307.68036
[9] Goldstine, J., Some independent families of one-letter languages, J. comput. system sci., 10, 351-369, (1975) · Zbl 0305.68059
[10] Gurari, E.M.; Ibarra, O.H., Simple counter machines and number-theoretic problems, J. comput. system sci., 19, 145-162, (1979) · Zbl 0426.68036
[11] Hartmanis, J.; Berman, L., On tape bounds for single-letter language processing, Theoret. comput. sci., 3, 213-224, (1973) · Zbl 0351.68014
[12] Ladner, R.E.; Lipton, R.J.; Stockmeyer, L.J., Alternating pushdown automata, (), 92-106
[13] Landau, E., (), 222-229
[14] Landau, E., Uber die maximalordung der permutationen gegebenen grades, Archiv. der math. und phys., 3, 92-103, (1903) · JFM 34.0233.02
[15] Liubicz, U.I., Bounds for the optimal determinization of nondeterministic autonomic automata, Sibirskii matemat. journal, 2, 337-355, (1964), (in Russian)
[16] Lupanov, O.B., A comparison of two types of finite automata, Problemy kibernetiki, 9, 321-326, (1963), (in Russian)
[17] Mendelsohn, N.S., A linear Diophantine equation with applications to nonnegative matrices, Ann. NY acad. sci., 175, 287-294, (1970) · Zbl 0225.10010
[18] Meyer, A.R.; Fischer, M.J., Economy of description by automata, grammars, and formal systems, (), 188-191
[19] Monien, B., The LBA-problem and the deterministic tape complexity of two-way, one-counter languages over a one-letter alphabet, Acta inform., 8, 371-382, (1977) · Zbl 0357.68073
[20] Monien, B., Two-way multihead automata over a one-letter alphabet, RAIRO inform. théor., 14, 67-82, (1980) · Zbl 0442.68039
[21] Rabin, M.; Scott, D., Finite automata and their decision problems, IBM J. res. dev., 3, 198-200, (1959) · Zbl 0158.25404
[22] Sakoda, W.J.; Sipser, M., Nondeterminism and the size of two-way finite automata, (), 275-286 · Zbl 1282.68160
[23] Schmidt, M., Succintness of description of context-free, regular and finite languages, ()
[24] Seiferas, J.I., Relating refined space complexity classes, J. comput. system sci., 14, 100-129, (1977) · Zbl 0352.68063
[25] Seiferas, J.I., Techniques for separating space complexity classes, J. comput. system sci., 14, 73-99, (1977) · Zbl 0352.68062
[26] Shepardson, J., The reduction of two-way automata to one-way automata, IBM J. res. dev., 3, 114-125, (1959)
[27] Sipser, M., Lower bounds on the size of sweeping automata, J. comput. system sci., 21, 195-202, (1980) · Zbl 0445.68064
[28] Szalay, M., On the maximal order in Sn and \(S\^{}\{∗\}n\), Acta arithm., 37, 321-331, (1980) · Zbl 0443.10029
[29] Trakhtenbort, B.A.; Barzdin, A.M., Finite automata, (1970), Nauka Moscow, (in Russian)
[30] Turan, P., Combinatorics, partitions, group theory, (), 181-200
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.