Automaticity IV : sequences, sets, and diversity

Shallit, Jeffrey 

Journal de théorie des nombres de Bordeaux, Tome 8 (1996) no. 2, pp. 347-367

Abstract (VO)

This paper studies the descriptional complexity of (i) sequences over a finite alphabet ; and (ii) subsets of $N$ (the natural numbers). If ${\left(s\left(i\right)\right)}_{i\ge 0}$ is a sequence over a finite alphabet $\Delta$, then we define the $k$-automaticity of $s,A_s^k\left(n\right)$, to be the smallest possible number of states in any deterministic finite automaton that, for all $i$ with $0\le i\le n$, takes $i$ expressed in base $k$ as input and computes $s\left(i\right)$. 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\left(n\right)=\Omega \left(n^{1/43}\right)$ for all $k\ge 2$, 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.

Résumé

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 ${\left(s\left(i\right)\right)}_{i\le 0}$ une suite sur un alphabet fini $\Delta$. Nous définissons la $k$-automaticité de s, notée $A_s^k\left(n\right)$, comme le plus petit nombre possible d’états d’un automate déterministe qui, pour tout $i$ tel que $0\le i\le n$, prend l’expression de $i$ en base $k$ comme entrée et calcule $s\left(i\right)$. 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\left(n\right)=\Omega \left(n^{1/43}\right)$ pour tout $k\ge 2$, 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.