Chrobak, Marek Finite automata and unary languages. (English) Zbl 0638.68096 Theor. Comput. Sci. 47, 149-158 (1986). 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. Cited in 5 ReviewsCited in 119 Documents MSC: 68Q45 Formal languages and automata Keywords:unary language; deterministic finite automata PDFBibTeX XMLCite \textit{M. Chrobak}, Theor. Comput. Sci. 47, 149--158 (1986; Zbl 0638.68096) 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, (Rept. 304 (1977), Polish Academy of Sciences) · 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, (Algebra i logika (seminar), 1 (1962)), 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, (Conf. Proc. IEEE 19th Ann. Symp. on Foundations of Computer Science (1978)), 92-106 [13] Landau, E., (Handbuch der Lehre von der Verteilung der Primzahlen I (1909), Teubner: Teubner Leipzig/Berlin), 222-229 · JFM 40.0232.08 [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, (Proc. 12th IEEE Symp. on Switching and Automata Theory (1971)), 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, (Proc. 10th ACM Symp. on Theory of Computing (1978)), 275-286 · Zbl 1282.68160 [23] Schmidt, M., Succintness of description of context-free, regular and finite languages, (Ph.D. Thesis (1978), Cornell University) [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 \(S_n\) and \(S^∗n\), Acta Arithm., 37, 321-331 (1980) · Zbl 0443.10029 [29] Trakhtenbort, B. A.; Barzdin, A. M., Finite Automata (1970), Nauka: Nauka Moscow, (in Russian) [30] Turan, P., Combinatorics, partitions, group theory, (Serge, B., Colloq. Internat. sulle Teorie Combinatorie (1976), Academia Nazionale dei Lincei: Academia Nazionale dei Lincei Rome), 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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.