Automata calculating the complexity of automatic sequences
The complexity of a sequence on a finite alphabet is the function \(n \to \rho (n)\), where \(\rho (n)\) is the number of factors (blocks) of length \(n\) of the sequence. In the case where the sequence is a fixed point of a uniform injective substitution and where the sequence takes only two values, the author shows that if the sequence is minimal, then \(n \to \rho (n+1) - \rho (n)\) is generated by an automaton which is explicitly constructed. Note that, as indicated by the author, B. Mossé has obtained more general results (Preprint, LMD). The paper ends with an example, the Thue-Morse sequence, for which the result of the author implies the previously known result of complexity [see \textit{A. de Luca} and \textit{S. Varricchio}, Theor. Comput. Sci. 63, 333-348 (1989; Zbl 0671.10050) and \textit{S. Brlek}, Discrete Appl. Math. 24, 83-96 (1989; Zbl 0683.20045)].
- Automata calculating the complexity of automatic sequences
- Enumeration of factors in the Thue-Morse word
- scientific article; zbMATH DE number 3114014 (Why is no real title available?)
- scientific article; zbMATH DE number 4198078 (Why is no real title available?)
- scientific article; zbMATH DE number 3811868 (Why is no real title available?)
- scientific article; zbMATH DE number 3926275 (Why is no real title available?)
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- Suites algébriques, automates et substitutions
- Uniform tag sequences
- Asymptotic subword complexity of fixed points of group substitutions
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- The ring of k-regular sequences
- Complexity and special factors
- Complexity of generalized Rudin-Shapiro sequences
- Automata calculating the complexity of automatic sequences
- Separators in infinite words generated by morphisms.
- Shift registers fool finite automata
- Special factors of automatic sequences
- On the subword complexity of Thue-Morse polynomial extractions
- Computing the prefix of an automaton
- On the D0L Repetition Threshold
- Calculating with Automata
- Représentation géométrique de suites de complexité 2n+1
- Entropy analysis of substitutive sequences revisited
- Reconnaissabilité des substitutions et complexité des suites automatiques
- Minimum complexity of automatic non sturmian sequences
- The subword complexity of fixed points of binary uniform morphisms
- Calculation of the complexities of substitutive sequences over a binary alphabet
- On the computational complexity of the Arnold complexity of binary words
- Subword complexity and k-synchronization
- Complexity of automatic sequences
- Complexity of automatic sequences
- Subword complexity of uniform D0L words over finite groups
- Automatic complexity of shift register sequences
- Behavior of various complexity functions
- On the context-freeness of the set of words containing overlaps
- On the permutation complexity of the Cantor-like sequences
This page was built for publication: Automata calculating the complexity of automatic sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1340682)
