Automaticity IV : sequences, sets, and diversity
Journal de théorie des nombres de Bordeaux, Volume 8 (1996) no. 2, p. 347-367

This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of N (the natural numbers). If (s(i)) i0 is a sequence over a finite alphabet Δ, then we define the k-automaticity of s,A s k (n), to be the smallest possible number of states in any deterministic finite automaton that, for all i with 0in, takes i expressed in base k as input and computes s(i). We give examples of sequences that have high automaticity in all bases k ; for example, we show that the characteristic sequence of the primes has k-automaticity A s k (n)=Ω(n 1/43 ) for all k2, thus making quantitative the classical theorem of Minsky and Papert that the set of primes expressed in base 2 is not regular. We give examples of sequences with low automaticity in all bases k, and low automaticity in some bases and high in others. We also obtain bounds on the automaticity of certain sequences that are fixed points of homomorphisms, such as the Fibonacci and Thue-Morse infinite words. Finally, we define a related concept called diversity and give examples of sequences with high diversity.

Dans cet article nous étudions la complexité de la description (i) de suites sur un alphabet fini et (ii) de sous-ensembles de l’ensemble N des entiers naturels. Soit (s(i)) i0 une suite sur un alphabet fini Δ. Nous définissons la k-automaticité de s, notée A s k (n), comme le plus petit nombre possible d’états d’un automate déterministe qui, pour tout i tel que 0in, prend l’expression de i en base k comme entrée et calcule s(i). Nous donnons des exemples de suites qui ont une grande automaticité dans toutes les bases k ; par exemple nous montrons que la k-automaticité de la fonction caractéristique des nombres premiers satisfait A s k (n)=Ω(n 1/43 ) pour tout k2, rendant ainsi quantitatif le théorème classique de Minsky et Papert suivant lequel l’ensemble des nombres premiers exprimés en base 2 n’est pas régulier. Nous donnons des exemples de suites dont la k-automaticité est petite dans toute base, ainsi que des exemples de suites dont la k-automaticité est petite dans certaines bases et grande dans d’autres. Nous obtenons aussi des bornes pour l’automaticité de certaines suites qui sont des points fixes d’homomorphismes, par exemple les mots infinis de Fibonacci et de Thue-Morse. Enfin nous définissons un concept voisin, appelé diversité, et nous donnons des exemples de suites ayant une diversité élevée.

@article{JTNB_1996__8_2_347_0,
     author = {Shallit, Jeffrey O.},
     title = {Automaticity IV : sequences, sets, and diversity},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux I},
     volume = {8},
     number = {2},
     year = {1996},
     pages = {347-367},
     zbl = {0876.11010},
     mrnumber = {1438474},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_1996__8_2_347_0}
}
Shallit, Jeffrey. Automaticity IV : sequences, sets, and diversity. Journal de théorie des nombres de Bordeaux, Volume 8 (1996) no. 2, pp. 347-367. http://www.numdam.org/item/JTNB_1996__8_2_347_0/

[1] D. Allen, Jr. On a characterization of the nonregular set of primes. J. Comput. System Sci. 2 (1968), 464-467. | MR 243939 | Zbl 0177.01903

[2] J.-P. Allouche, A. Arnold, J. Berstel, S. Brlek, W. Jockusch, S. Plouffe, and B.E. Sagan. A relative of the Thue-Morse sequence. Discrete Math. 139 (1995), 455-461. | MR 1336854 | Zbl 0839.11007

[3] J. Berstel. Recent results on Sturmian words. To appear, Proc. of DLT '95. Also available at http: //www-litp. ibp fr/berstel/Liaisons/magdeburg. ps . gz.

[4] J.W.S. Cassels. An Introduction to Diophantine Approximation. Cambridge University Press,1957. | MR 87708 | Zbl 0077.04801

[5] A. Cobham. Uniform tag sequences. Math. Systems Theory 6 (1972),164-192. | MR 457011 | Zbl 0253.02029

[6] D. Crisp, W. Moran, A. Pollington, and P. Shiue. Substitution invariant cutting sequences. J. Théorie Nombres Bordeaux 5 (1993),123-137. | Numdam | MR 1251232 | Zbl 0786.11041

[7] C. Dwork and L. Stockmeyer. On the power of 2-way probabilistic finite state automata. In Proc. 30th Ann. Symp. Found. Comput. Sci., pages 480-485. IEEE Press, 1989.

[8] C. Dwork and L. Stockmeyer. A time complexity gap for two-way probabilistic finite-state automata. SIAM J. Comput. 19 (1990), 1011-1023. | MR 1069095 | Zbl 0711.68075

[9] S. Eilenberg. Automata, Languages, and Machines, Vol. A. Academic Press, 1974. | MR 530382 | Zbl 0317.94045

[10] I. Glaister and J. Shallit. Automaticity III: Polynomial automaticity and context-free languages. Submitted,1996.

[11] G.H. Hardy and E.M. Wright. An Introduction to the Theory of Numbers. Oxford University Press, 1989. | MR 568909

[12] J. Hartmanis and H. Shank. On the recognition of primes by automata. J. Assoc. Comput. Mach. 15 (1968), 382-389. | MR 235916 | Zbl 0164.05201

[13] D.R. Heath-Brown. The least square-free number in an arithmetic progression. J. Reine Angew. Math. 332 (1982), 204-220. | MR 656864 | Zbl 0493.10045

[14] D.R. Heath-Brown. Zero-free regions for Dirichlet L-functions and the least prime in an arithmetic progression. Proc. Lond. Math. Soc. 64 (1992), 265-338. | MR 1143227 | Zbl 0739.11033

[15] J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979. | MR 645539 | Zbl 0426.68001

[16] J. Kaneps and R. Freivalds. Minimal nontrivial space complexity of probabilistic one-way Turing machines. In B. Rovan, editor, MFCS '90 (Mathematical Foundations of Computer Science), Vol. 452 of Lecture Notes in Computer Science, pages 355-361. Springer-Verlag, 1990. | MR 1084853 | Zbl 0762.68019

[17] J. Kaneps and R. Freivalds. Running time to recognize nonregular languages by 2-way probabilistic automata. In J. Leach Albert, B. Monien, and M. Rodríguez Artalejo, editors, ICALP '91 (18th International Colloquium on Automata, Languages, and Programming), Vol. 510 of Lecture Notes in Computer Science, pages 174-185. Springer-Verlag, 1991. | MR 1129905 | Zbl 0766.68098

[18] D.E. Knuth. The Art of Computer Programming, Vol. III: Sorting and Searching. Addison-Wesley, 1973. | MR 378456 | Zbl 0302.68010

[19] M. Minsky and S. Papert. Unrecognizable sets of numbers. J. Assoc. Comput. Mach. 13 (1966), 281-286. | MR 207481 | Zbl 0166.00601

[20] C. Pomerance, J.M. Robson, and J.O. Shallit. Automaticity II: Descriptional complexity in the unary case. To appear, Theoret. Comput. Sci. | MR 1453865 | Zbl 0959.11015

[21] J.B. Rosser and L. Schoenfeld. Approximate formulas for some functions of prime numbers. Ill. J. Math. 6 (1962), 64-94. | MR 137689 | Zbl 0122.05001

[22] L. Schoenfeld. Sharper bounds for the Chebyshev functions θ(x) and ψ(x). II. Math. Comp. 30 (1976), 337-360. Corrigenda in Math. Comp. 30 (1976), 900. | Zbl 0326.10037

[23] J. Shallit. Some facts about continued fractions that should be better known. Technical Report CS-91-30, University of Waterloo, Department of Computer Science, July 1991.

[24] J. Shallit. The fixed point of 1→ 121, 2 → 12221 is not 2-automatic. Unpublished manuscript, dated September 10, 1992.

[25] J. Shallit. Real numbers with bounded partial quotients: a survey. Enseign. Math. 38 (1992),151-187. | MR 1175525 | Zbl 0753.11006

[26] J. Shallit and Y. Breitbart. Automaticity: Properties of a measure of descriptional complexity. In P. Enjalbert, E. W. Mayr, and K. W. Wagner, editors, STACS 94: 11th Annual Symposium on Theoretical Aspects of Computer Science, Vol. 775 of Lecture Notes in Computer Science, pages 619-630. Springer-Verlag, 1994. | MR 1288529

[27] J. Shallit and Y. Breitbart. Automaticity I: Properties of a measure of descriptional complexity. To appear, J. Comput. System Sci. | MR 1409007 | Zbl 0859.68059

[28] N.B. Slater. Gaps and steps for the sequence nθ mod 1. Proc. Cambridge Phil. Soc. 63 (1967), 1115-1123. | Zbl 0178.04703

[29] V.T. Sós. On the distribution mod 1 of the sequence nα. Ann. Univ. Sci. Budapest Eötvös Sect. Math. 1 (1958),127-134. | Zbl 0094.02903

[30] S. Swierczkowski. On successive settings of an arc on the circumference of a circle. Fundamenta Math. 46 (1958), 187-189. | MR 104651 | Zbl 0085.27203

[31] S.S. Wagstaff, Jr. Greatest of the least primes in arithmetic progressions having a given modulus. Math. Comp. 33 (1979), 1073-1080. | MR 528061 | Zbl 0407.10034