SMF

Reconnaissabilité des substitutions et complexité des suites automatiques

Brigitte Mossé
Reconnaissabilité des substitutions et complexité des suites automatiques
  • Année : 1996
  • Fascicule : 2
  • Tome : 124
  • Format : Électronique
  • Langue de l'ouvrage :
    Français
  • Class. Math. : 11~J~70, 58~F~11, 60~F~05
  • Pages : 329-346
  • DOI : 10.24033/bsmf.2283
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.
We first recall some notions and one theorem of recognizability about infinite words fixed points of primitive substitutions. When the length of the substitution is constant equal to $q$, we study the complexity function $p(n)$ of the fixed point $u$, which is the number of factors of $u$ of length $n$. We give a method to compute $p(n)$ with linear recurrence formulas and we prove that the sequence $(p(n+1) -p(n))_{n\in \mathbb {N}}$ is $q$-automatic.


Des problèmes avec le téléchargement?Des problèmes avec le téléchargement?
Informez-nous de tout problème que vous avez...