×

Recognizability of substitutions and complexity of automatic sequences. (Reconnaissabilité des substitutions et complexité des suites automatiques.) (French) Zbl 0855.68072

Summary: 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.

MSC:

68R15 Combinatorics on words
68Q45 Formal languages and automata

Keywords:

recognizability
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[1] ALLOUCHE (J.-P.) . - Sur la complexité des suites infinies , prépublication. · Zbl 0803.68094
[2] ALLOUCHE (J.-P.) et SHALLIT (J.) . - The ring of k-regular sequences , Theoret. Comput. Sci., t. 98, 1992 , p. 163-187. MR 94c:11021 | Zbl 0774.68072 · Zbl 0774.68072
[3] CHRISTOL (G.) , KAMAE (T.) , MENDES-FRANCE (M.) et RAUZY (G.) . - Suites algébriques, automates et substitutions , Bull. Soc. Math. France, t. 108, 1980 , p. 401-419. Numdam | MR 82e:10092 | Zbl 0472.10035 · Zbl 0472.10035
[4] DEKKING (F.-M.) . - Combinatorial and statistical properties of sequences generated by substitutions , Thèse, Nijmegen, 1980 .
[5] GABRIEL (P.) . - Communication privée .
[6] HOST (B.) . - Valeurs propres des systèmes dynamiques définis par des substitutions de longueur variable , Ergodic Theory Dynamical Systems, t. 6, 1986 , p. 529-540. MR 88i:26007 | Zbl 0625.28011 · Zbl 0625.28011
[7] MARTIN (J.-C.) . - Minimal flows arising from substitutions of non constant length , Math. Systems Theory, t. 7, 1973 , p. 73-82. MR 48 #3029 | Zbl 0256.54026 · Zbl 0256.54026
[8] MOSSÉ (B.) . - Puissances de mots et reconnaissabilité des points fixes de substitutions , Theoret. Comput. Sci., t. 99, 1992 , p. 327-334. MR 93f:68076 | Zbl 0763.68049 · Zbl 0763.68049
[9] QUEFFÉLEC (M.) . - Substitution dynamical systems - Spectral analysis , Lecture Notes in Math., t. 1294, 1987 . MR 89g:54094 | Zbl 0642.28013 · Zbl 0642.28013
[10] TAPSOBA (T.) . - Complexité de suites automatiques , Thèse de 3e cycle, Aix-Marseille II, 1987 .
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.