Automates calculant la complexité de suites automatiques

Tapsoba, Théodore 

Journal de théorie des nombres de Bordeaux, Tome 6 (1994) no. 1, pp. 127-134

Résumé (VO)

Le point fixe $u$ d’une substitution injective uniforme de module $\sigma$ sur un alphabet $A$ est examiné du point de vue du nombre $P(u,n)$ de ses blocs distincts de longueur $n$. Lorsque $u$ est minimal et $A$ de cardinal deux, nous construisons un automate pour la suite $n\to P(u,n+1)-P(u,n)$.

Abstract

A fixed point $u$ of an injective substitution of constant length $\sigma$ on an alphabet $A$ is considered in relation with the number $P(u,n)$ of its distinct $n$-blocks. When $u$ is minimal and $A$ a set of two elements, we prove that the sequence $n\to P(u,n+1)-P(u,n)$ is obtained by an automaton which is built explicitly.