×

zbMATH — the first resource for mathematics

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
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
PDF BibTeX XML Cite
Full Text: DOI
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 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, () · 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), () · JFM 39.0283.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.