RECONNAISSABILITE DES SUBSTITUTIONS ET COMPLEXITE DES SUITES AUTOMATIQUES

摘要

Nous rappelons tout d'abord en les completant quelques notions et uti Soreme de reconnaissabilite concernant les mots infinis points fixes de substitutions timitiveM. Dans le cas ou'la substitution considered est de longueur constante q, nous dJons la fonction de complexity p du point fixe u, cest-ardire le nombre de de longueur n de u. Nous dpnnons une methode pour calculer p(n),par des de recurrence linfiaire et nous montrons-que la suite (p(n + 1) — p(n))neN est q-automa ique. We first recall some notions and one theorem of jecogriizabili-ty inf uite words fixed points of primitive substitutions. When the length of the Slifc>stituti mi is constant equal to q, we study the complexity function p(n) of the fl poii.t u, which is the number of factors, of u.of length n. We give a method compvte p(n) with linear recurrence formulas and we prove thftt the sequence (p(n+1) -p(n)),l6m is g-automatic.