A characterization of words of linear complexity

DOI10.1090/PROC/14440MaRDI QIDQ5384833zbMATH OpenOpenAlexWikidataFDO

Authors Julien Cassaigne, Svetlana Puzynina, Luca Q. Zamboni, Anna Frid

Publication date 26 June 2019

Published in Proceedings of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1090/proc/14440

zbMATH Keywords

factor complexitylinear complexitySturmian words

Mathematics Subject Classification ID

Symbolic dynamics (37B10) Combinatorics on words (68R15)

Recommendations

• On the character of words of sublinear complexity
• Words whose complexity satisfies lim \(\frac{p(n)}{n} = 1\).
• Factor complexity
• Infinite words with linear subword complexity
• Subword complexity and decomposition of the set of factors

Cites work

• Automatic Sequences
• Complexité des facteurs des mots infinis engendrés par morphismes itérés
• Enumeration of factors in the Thue-Morse word
• Episturmian words: a survey
• Factor complexity
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 2183071 (Why is no real title available?)
• scientific article; zbMATH DE number 5051582 (Why is no real title available?)
• Sequences with subword complexity \(2n\)
• SMALL DENOMINATORS AND PROBLEMS OF STABILITY OF MOTION IN CLASSICAL AND CELESTIAL MECHANICS
• Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
• Some improvements of the S-adic conjecture
• Substitution dynamical systems - spectral analysis
• Substitutions in dynamics, arithmetics and combinatorics
• Subword complexities of various classes of deterministic developmental languages without interactions
• Subword complexity and decomposition of the set of factors
• Symbolic Dynamics II. Sturmian Trajectories

Cited in

(9)

• Subword complexity and decomposition of the set of factors
• The Average State Complexity of the Star of a Finite Set of Words Is Linear
• On the character of words of sublinear complexity
• scientific article; zbMATH DE number 6861068 (Why is no real title available?)
• Factor complexity
• Proof of a conjecture on word complexity
• Linear complexity words and surface laminations
• Characterizations of families of morphisms and words via binomial complexities
• Measure-theoretically mixing subshifts of minimal word complexity

This page was built for publication: A characterization of words of linear complexity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5384833)