On the arithmetical complexity of Sturmian words

DOI10.1016/j.tcs.2007.03.022zbMath1119.68138MaRDI QIDQ2373754

Julien Cassaigne, Anna E. Frid

Publication date: 16 July 2007

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

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

zbMATH Keywords

infinite word; Sturmian word; subword complexity; arithmetical complexity; Fibonacci word; rotation word

Mathematics Subject Classification ID

68R15: Combinatorics on words

Related Items

Computing the \(k\)-binomial complexity of the Thue-Morse word, Monochromatic arithmetic progressions in binary Thue-Morse-like words, On the Lie complexity of Sturmian words, Asymptotic formula for balanced words, On possible growths of arithmetical complexity, Sequences of low arithmetical complexity, Sturmian and Episturmian Words

Cites Work

• Unnamed Item
• Sequences of linear arithmetical complexity
• *-Sturmian words and complexity
• Complexity of sequences and dynamical systems
• Sequences with subword complexity \(2n\)
• Arithmetical complexity of symmetric D0L words.
• A lower bound for the arithmetical complexity of Sturmian words
• On possible growths of arithmetical complexity
• Sequences of low arithmetical complexity
• A GEOMETRIC PROOF OF THE ENUMERATION FORMULA FOR STURMIAN WORDS
• A remark on morphic sturmian words
• Sequence entropy and the maximal pattern complexity of infinite words