Automata calculating the complexity of automatic sequences (Q1340682): Difference between revisions

From MaRDI portal
RedirectionBot (talk | contribs)
Removed claim: reviewed by (P1447): Item:Q187638
Import241208061232 (talk | contribs)
Normalize DOI.
 
(4 intermediate revisions by 4 users not shown)
Property / DOI
 
Property / DOI: 10.5802/jtnb.109 / rank
Normal rank
 
Property / reviewed by
 
Property / reviewed by: Jean-Paul Allouche / rank
 
Normal rank
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W2314536985 / rank
 
Normal rank
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
Property / DOI
 
Property / DOI: 10.5802/JTNB.109 / rank
 
Normal rank

Latest revision as of 18:23, 10 December 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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references