Automata calculating the complexity of automatic sequences (Q1340682): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
ReferenceBot (talk | contribs) Changed an Item |
||
Property / cites work | |||
Property / cites work: Q3700861 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Enumeration of factors in the Thue-Morse word / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Suites algébriques, automates et substitutions / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Uniform tag sequences / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3228119 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3659988 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3348040 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Automata calculating the complexity of automatic sequences / rank | |||
Normal rank |
Revision as of 09:57, 23 May 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Automata calculating the complexity of automatic sequences |
scientific article |
Statements
Automata calculating the complexity of automatic sequences (English)
0 references
9 July 1995
0 references
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)].
0 references
automatic sequences
0 references
complexity
0 references
Thue-Morse sequence
0 references