Power of words and recognizability of fixpoints of a substitution. (Puissances de mots et reconnaissabilité des points fixes d’une substitution.) (French) Zbl 0763.68049

Mossé, Brigitte

Theor. Comput. Sci. 99, No. 2, 327-334 (1992).

Soit \({\mathcal A}\) un ensemble fini de cardinal \(g\geq 2\), appelé alphabet, et \(\sigma\) une substitution sur \({\mathcal A}\), c’est-à-dire une application de \({\mathcal A}\) dans \({\mathcal A}^*\) prolongée par concaténation à \({\mathcal A}^*\) et à \({\mathcal A}^ \mathbb{N}\), admettant un point fixe \(u\) non périodique. Nous montrons que pour \(N\) assez grand \(u\) ne contient aucune puissance \(N\)-ème de mot pour la concaténation si l’on fait l’hypothèse que \(\sigma\) est primitive. Nous donnons ensuite une condition nécessaire et suffisante pour que \(\sigma\) soit reconnaissable au sens de B. Host [Ergodic Theory Dyn. Syst. 6, 529-540 (1986; Zbl 0625.28011)] et M. Queffélec [Substitution dynamical systems-spectral analyses, Lect. Notes Math. 1294, Berlin, Springer-Verlag (1987; Zbl 0642.28013)], et nous montrons qu’il suffit de “bilatéraliser” cette définition pour obtenir une propriété vérifiée cette fois par toutes les substitutions primitives à point fixe non périodique: il existe un entier \(L>0\) tel que si \(u(i-L)\dots u(i+L)=u(j-L)\dots u(j+L)\), et \(i\in E_ 1=\{0\}\cup\{|\sigma(u[0,p-1])|\); \(p>0\}\) alors \(j\in E_ 1\).

Reviewer: B.Mossé

MSC:

68Q45

Formal languages and automata

Citations:

Zbl 0625.28011; Zbl 0642.28013

References:

[1]	Dekking, F. M., Combinatorial and statistical properties of sequences generated by substitutions, Thèse (1980), Nijmegen · Zbl 0438.10040
[2]	Host, B., Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable, Ergodic Theory and Dynamical Systems, 6, 529-540 (1986) · Zbl 0625.28011
[3]	Lothaire, M., Combinatorics on Words (1983), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0514.20045
[4]	Martin, J. C., Minimal flows arising from substitutions of non constant length, Math. Systems Theory, 7, 73-82 (1973) · Zbl 0256.54026
[5]	Queffélec, M., Substitution dynamical systems—Spectral analysis, (Lecture Notes in Mathematics, Vol. 1294 (1987), Springer: Springer Berlin) · Zbl 0642.28013
[6]	Séébold, P., Propriété combinatoires des mots infinis engendrés par certains morphismes, Thèse de Doctorat, 16-85 (1985), Rapport L.I.T.P.
[7]	Séébold, P., An effective solution to the DOL periodicity problem in the binary case, EATCS Bull., 36, 137-151 (1988) · Zbl 0678.68072
[8]	Thue, A., Über unendliche Zeichenreihen (1906), (Selected Mathematical Papers of Axel Thue (1977), Universitetsforlaget) · JFM 39.0283.01