# 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).

##### MSC:
 11B85 Automata sequences 68Q45 Formal languages and automata 68R15 Combinatorics on words
##### Keywords:
deterministic automaticity; languages
Full Text:
##### References:
  Allender, E.W., On the number of cycles possible in digraphs with large girth, Discrete appl. math., 10, 211-225, (1985) · Zbl 0565.05049  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  Alt, H.; Mehlhorn, K., A language over a one symbol alphabet requiring only o(loglogn) space, SIGACT news, 7, 4, 31-33, (1975)  Bach, E., Explicit bounds for primality testing and related problems, Math. comp., 55, 355-380, (1990) · Zbl 0701.11075  Bach, E.; Huelsbergen, L., Statistical evidence for small generating sets, Math. comp., 61, 69-82, (1993) · Zbl 0784.11059  Berstel, J.; de Fibonacci, Mots, (), 57-78  Berstel, J., Fibonacci words — a survey, (), 13-27  Brown, D.R.L.; Davidson, K.R.; Shallit, J., Elementary problem proposal 10433, Amer. math. monthly, 102, 170, (1995)  Chrobak, M., Finite automata and unary languages, Theoret. comput. sci., 47, 149-158, (1986) · Zbl 0638.68096  Chuan, W.-F., Extraction property of the Golden sequence, Fibonacci quart., 33, 113-122, (1995) · Zbl 0842.11007  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  Dénes, J.; Kim, K.H.; Roush, F.W., Automata on one symbol, (), 127-134 · Zbl 0527.68038  Dwork, C.; Stockmeyer, L., On the power of 2-way probabilistic finite state automata, (), 480-485  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  Feller, W., ()  Garel, E., Conjecture 14 de shallit et séparateurs, (August, 1995), unpublished manuscript  Glaister, I.; Shallit, J., Polynomial automaticity, context-free languages, and fixed points of morphisms, (), 382-393 · Zbl 0889.68093  Hopcroft, J.E.; Ullman, J.D., Introduction to automata theory, languages, and computation, (1979), Addison-Wesley Reading, MA · Zbl 0196.01701  Kaneps, J.; Freivalds, R., Minimal nontrivial space complexity of probabilistic one-way Turing machines, (), 355-361 · Zbl 0762.68019  Kaneps, J.; Freivalds, R., Running time to recognize nonregular languages by 2-way probabilistic automata, (), 174-185 · Zbl 0766.68098  Karhumäki, J., On cube-free co-words generated by binary morphisms, Discrete appl. math., 5, 279-297, (1983) · Zbl 0505.03022  Karp, R.M., Some bounds on the storage requirements of sequential machines and Turing machines, J. ACM, 14, 478-489, (1967) · Zbl 0153.31802  Knuth, D.E., The art of computer programming, vol. 1: fundamental algorithms, (1973), Addison-Wesley Reading, MA · Zbl 0191.17903  Kosaraju, S.R., On independent circuits of a digraph, J. graph theory, 1, 379-382, (1977) · Zbl 0383.05020  Lekkerkerker, C.G., Voorstelling Van natuurlijke getallen door een som Van getallen Van Fibonacci, Simon stevin, 29, 190-195, (1952) · Zbl 0049.03101  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  Lyubich, Ju.I., Estimates for optimal determinization of nondeterministic autonomous automata, Sibirskii matematicheskii zhurnal, 5, 337-355, (1964), (in Russian) · Zbl 0192.08104  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  Mandl, R., Precise bounds associated with the subset construction on various classes of nondeterministic finite automata, (), 263-267  Rauzy, G., Suites à termes dans un alphabet fini, (), 25.01-25.16  Rosser, J.B.; Schoenfeld, L., Approximate formulas for some functions of prime numbers, Illinois J. math., 6, 64-94, (1962) · Zbl 0122.05001  Shallit, J.; Breitbart, Y., Automaticity: properties of a measure of descriptional complexity, (), 619-630  Shallit, J.; Breitbart, Y., Automaticity I: properties of a measure of descriptional complexity, J. comput. system sci., 53, 10-25, (1996) · Zbl 0859.68059  Thomassen, C., On digraphs with no two disjoint cycles, Combinatorica, 7, 145-150, (1987) · Zbl 0628.05034  Williams, H.C.; Shallit, J.O., Factoring integers before computers, (), 481-531 · Zbl 0847.11002  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.