Automaticity. II: Descriptional complexity in the unary case. (English) Zbl 0959.11015

Summary: Let \(\Sigma\) and \(\Delta\) be finite alphabets, and let \(f\) be a map from \(\Sigma^{*}\) to \(\Delta\). Then the deterministic automaticity of \(f\), \(A_{f}(n)\), is defined to be the size of the minimum finite-state machine that correctly computes \(f\) on all inputs of size \(<n\). A similar definition applies to languages \(L\). We denote the nondeterministic analogue (for languages \(L)\) of automaticity by \(N_{L}(n)\). In a previous paper, J. Shallit and Yu. Breitbart [J. Comput. Syst. Sci. 51, 10-25 (1996; Zbl 0859.68059)] examined the properties of this measure of descriptional complexity in the case \(|\Sigma |\geqslant 2\).
In this paper, we continue the study of automaticity, focusing on the case where \(|\Sigma |=1\). We prove that \(A_{f}(n)<n+1-\lfloor \log_{\ell} n\rfloor\), where \(\ell =|\Delta |\). We also prove that \(A_{f}(n)>n-2 \log_{\ell} n-2 \log_{\ell}\log_{\ell} n\) for almost all functions \(f\). In the nondeterministic case, we show that there exists a \(c\) such that for almost all unary languages \(L\), we have \(N_{L}(n)>cn/\log n\) for all sufficiently large \(n\). The proof is based on a new enumeration method for languages accepted by unary \(q\)-state NFAs. If \(L\) is not a regular language, then it follows from a result of Karp that \(\limsup_{n\rightarrow \infty}A_{L}(n)/n\geqslant \frac{1}{2}\). We conjecture that if \(L\subseteq 0^{*}\), then this bound can be improved to \((5-1)/2\). Finally, we give some lower bounds for nondeterministic automaticity for nonregular languages. For Parts III and IV, cf. Comput. Complexity 7, 371-387 (1998); J. Théor. Nombres Bordx. 8, 347-367 (1996; Zbl 0876.11010).


11B85 Automata sequences
68Q45 Formal languages and automata
68R15 Combinatorics on words
Full Text: DOI


[1] Allender, E. W., On the number of cycles possible in digraphs with large girth, Discrete Appl. Math., 10, 211-225 (1985) · Zbl 0565.05049
[2] Allouche, J.-P.; Bousquet-Mélou, M., On the conjectures of Rauzy and Shallit for infinite words, Comment. Math. Univ. Carolinae, 36, 705-711 (1995) · Zbl 0859.11019
[3] Alt, H.; Mehlhorn, K., A language over a one symbol alphabet requiring only \(o( log log n)\) space, SIGACT News, 7, 4, 31-33 (1975)
[4] Bach, E., Explicit bounds for primality testing and related problems, Math. Comp., 55, 355-380 (1990) · Zbl 0701.11075
[5] Bach, E.; Huelsbergen, L., Statistical evidence for small generating sets, Math. Comp., 61, 69-82 (1993) · Zbl 0784.11059
[6] Berstel, J.; de Fibonacci, Mots, (Séminaire d’Informatique Théorique (1980/1981), Laboratoire Informatique Théorique, Institut Henri Poincaré), 57-78
[7] Berstel, J., Fibonacci words — a survey, (Rozenberg, G.; Salomaa, A., The Book of L (1986), Springer: Springer Berlin), 13-27 · Zbl 0589.68053
[8] Brown, D. R.L.; Davidson, K. R.; Shallit, J., Elementary problem proposal 10433, Amer. Math. Monthly, 102, 170 (1995)
[9] Chrobak, M., Finite automata and unary languages, Theoret. Comput. Sci., 47, 149-158 (1986) · Zbl 0638.68096
[10] Chuan, W.-F., Extraction property of the golden sequence, Fibonacci Quart., 33, 113-122 (1995) · Zbl 0842.11007
[11] Condon, A.; Hellerstein, L.; Pottle, S.; Wigderson, A., On the power of finite automata with both nondeterministic and probabilistic states, (Proc. 26th Ann. ACM Symp. Theor. Comput. (1994), ACM: ACM New York), 676-685 · Zbl 1345.68203
[12] Dénes, J.; Kim, K. H.; Roush, F. W., Automata on one symbol, (Studies in Pure Mathematics: To the Memory of Paul Turán (1983), Birkhäuser: Birkhäuser Basel), 127-134 · Zbl 0527.68038
[13] Dwork, C.; Stockmeyer, L., On the power of 2-way probabilistic finite state automata, (Proc. 30th Ann. Symp. Found. Comput. Sci. (1989), IEEE Press: IEEE Press New York), 480-485
[14] Dwork, C.; Stockmeyer, L., A time complexity gap for two-way probabilistic finite-state automata, SIAM J. Comput., 19, 1011-1023 (1990) · Zbl 0711.68075
[15] Feller, W., (An Introduction to Probability Theory and its Applications, Vol. I (1957), Wiley: Wiley New York) · Zbl 0077.12201
[16] Garel, E., Conjecture 14 de Shallit et séparateurs (August, 1995), unpublished manuscript
[17] Glaister, I.; Shallit, J., Polynomial automaticity, context-free languages, and fixed points of morphisms, (Penczek, W.; Szałas, A., Proc. 21st Internat. Symp. Mathematical Foundations of Computer Science. Proc. 21st Internat. Symp. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, Vol. 1113 (1996), Springer: Springer Berlin), 382-393 · Zbl 0889.68093
[18] Hopcroft, J. E.; Ullman, J. D., Introduction to Automata Theory, Languages, and Computation (1979), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0196.01701
[19] Kaneps, J.; Freivalds, R., Minimal nontrivial space complexity of probabilistic one-way Turing machines, (Rovan, B., MFCS ’90 (Mathematical Foundations of Computer Science). MFCS ’90 (Mathematical Foundations of Computer Science), Lecture Notes in Computer Science, Vol. 452 (1990), Springer: Springer Berlin), 355-361 · Zbl 0762.68019
[20] Kaneps, J.; Freivalds, R., Running time to recognize nonregular languages by 2-way probabilistic automata, (Albert, J. Leach; Monien, B.; Artalejo, M. Rodríguez, ICALP ’91 (18th International Colloquium on Automata, Languages, and Programming). ICALP ’91 (18th International Colloquium on Automata, Languages, and Programming), Lecture Notes in Computer Science, Vol. 510 (1991), Springer: Springer Berlin), 174-185 · Zbl 0766.68098
[21] Karhumäki, J., On cube-free co-words generated by binary morphisms, Discrete Appl. Math., 5, 279-297 (1983) · Zbl 0505.03022
[22] Karp, R. M., Some bounds on the storage requirements of sequential machines and Turing machines, J. ACM, 14, 478-489 (1967) · Zbl 0153.31802
[23] Knuth, D. E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms (1973), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0191.17903
[24] Kosaraju, S. R., On independent circuits of a digraph, J. Graph Theory, 1, 379-382 (1977) · Zbl 0383.05020
[25] Lekkerkerker, C. G., Voorstelling van natuurlijke getallen door een som van getallen van Fibonacci, Simon Stevin, 29, 190-195 (1952) · Zbl 0049.03101
[26] Lyubich, Ju. I., Soviet Math., 5, 345-348 (1964), an English translation appears in · Zbl 0131.01003
[27] Lyubich, Ju. I., Estimates for optimal determinization of nondeterministic autonomous automata, Sibirskii Matematicheskii Zhurnal, 5, 337-355 (1964), (in Russian) · Zbl 0192.08104
[28] Lyubich, Ju. I.; Livshits, E. M., Estimates for the weight of a regular event over a 1-letter alphabet, Sibirskii Matematicheskii Zhurnal, 6, 122-126 (1965), (in Russian). · Zbl 0158.01004
[29] Mandl, R., Precise bounds associated with the subset construction on various classes of nondeterministic finite automata, (Proc. 7th Princeton Conf. on Information and System Sciences (1973)), 263-267
[30] Rauzy, G., Suites à termes dans un alphabet fini, (Sém. de Théorie des Nombres de Bordeaux (1982 1983)), 25.01-25.16 · Zbl 0547.10048
[31] Rosser, J. B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Illinois J. Math., 6, 64-94 (1962) · Zbl 0122.05001
[32] Shallit, J.; Breitbart, Y., Automaticity: Properties of a measure of descriptional complexity, (Enjalbert, P.; Mayr, E. W.; Wagner, K. W., STAGS 94: 11th Annual Symp. Theoretical Aspects of Computer Science. STAGS 94: 11th Annual Symp. Theoretical Aspects of Computer Science, Lecture Notes in Computer Science, Vol. 775 (1994), Springer: Springer Berlin), 619-630
[33] Shallit, J.; Breitbart, Y., Automaticity I: Properties of a measure of descriptional complexity, J. Comput. System Sci., 53, 10-25 (1996) · Zbl 0859.68059
[34] Thomassen, C., On digraphs with no two disjoint cycles, Combinatorica, 7, 145-150 (1987) · Zbl 0628.05034
[35] Williams, H. C.; Shallit, J. O., Factoring integers before computers, (Gautschi, W., Mathematics of Computation, 1943-1993: A Half-Century of Computational Mathematics, Proc. Symposia Appl. Math., Vol. 48 (1994), American Mathematical Society: American Mathematical Society Providence, RI), 481-531 · Zbl 0847.11002
[36] Zeckendorf, E., Représentation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Royale des Sciences de Liège, 41, 3-4, 179-182 (1972) · Zbl 0252.10011
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.