Sequences of linear arithmetical complexity

DOI10.1016/J.TCS.2005.01.009zbMath1076.68053OpenAlexW2056306675MaRDI QIDQ557917

Anna E. Frid

Publication date: 30 June 2005

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2005.01.009

zbMATH Keywords

\(S\)-adic conjectureArithmetical complexityInfinite wordSpecial wordsSubword complexityToeplitz wordUniformly recurrent word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Related Items (12)

On the arithmetical complexity of Sturmian words ⋮ Non-injectivity of infinite interval exchange transformations and generalized Thue-Morse sequences ⋮ Monochromatic arithmetic progressions in automatic sequences with group structure ⋮ On possible growths of Toeplitz languages ⋮ Language structure of pattern Sturmian words ⋮ Constructing Infinite Words of Intermediate Arithmetical Complexity ⋮ Computing the \(k\)-binomial complexity of the Thue-Morse word ⋮ Uniform sets and complexity ⋮ On possible growths of arithmetical complexity ⋮ Sequences of low arithmetical complexity ⋮ Monochromatic arithmetic progressions in binary Thue-Morse-like words ⋮ Repetitions in Toeplitz words and the Thue threshold

Cites Work

• Unnamed Item
• Unnamed Item
• The ring of \(k\)-regular sequences
• Subword complexities of various classes of deterministic developmental languages without interactions
• Complexity and special factors
• Complexity of sequences and dynamical systems
• Toeplitz words, generalized periodicity and periodically iterated morphisms
• Complexity of Toeplitz sequences
• Arithmetical complexity of symmetric D0L words.
• Local symmetries in the period-doubling sequence
• Sequences of low arithmetical complexity
• Sequence entropy and the maximal pattern complexity of infinite words

This page was built for publication: Sequences of linear arithmetical complexity