zbMATH — the first resource for mathematics

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(loglogn) 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, (), 57-78
[7] Berstel, J., Fibonacci words — a survey, (), 13-27
[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, (), 676-685 · Zbl 1345.68203
[12] Dénes, J.; Kim, K.H.; Roush, F.W., Automata on one symbol, (), 127-134 · Zbl 0527.68038
[13] Dwork, C.; Stockmeyer, L., On the power of 2-way probabilistic finite state automata, (), 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., ()
[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, (), 382-393 · Zbl 0889.68093
[18] Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701
[19] Kaneps, J.; Freivalds, R., Minimal nontrivial space complexity of probabilistic one-way Turing machines, (), 355-361 · Zbl 0762.68019
[20] Kaneps, J.; Freivalds, R., Running time to recognize nonregular languages by 2-way probabilistic automata, (), 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 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.; Lyubich, Ju.I., Estimates of the number of states that arise in the determinization of a nondeterministic autonomous automaton, Dokl. akad. nauk SSSR, 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, (), 263-267
[30] Rauzy, G., Suites à termes dans un alphabet fini, (), 25.01-25.16
[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, (), 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, (), 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. 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.