Reconnaissabilité des substitutions et complexité des suites automatiques
Français
Nous rappelons tout d'abord en les complétant quelques notions et un théorème de reconnaissabilité concernant les mots infinis points fixes de substitutions primitives. Dans le cas où la substitution considérée est de longueur constante $q$, nous étudions la fonction de complexité $p(n)$ du point fixe $u$, c'est-à-dire le nombre de facteurs de longueur $n$ de $u$. Nous donnons une méthode pour calculer $p(n)$ par des formules de récurrence linéaire et nous montrons que la suite $(p(n+1) -p(n))_{n\in \mathbb {N}}$ est $q$-automatique.
algorithme de théorèmes limites