Infinite words with linear subword complexity
From MaRDI portal
Publication:1824405
DOI10.1016/0304-3975(89)90046-7zbMath0682.68083OpenAlexW2010717857MaRDI QIDQ1824405
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90046-7
subword complexityinfinite wordslinear complexity and combinatorial propertiessturmian infinite words
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Continued fractions (11A55) Radix representation; digital problems (11A63)
Related Items
Occurrences of palindromes in characteristic Sturmian words, Abelian-square-rich words, Abelian powers and repetitions in Sturmian words, Moments of conjugacy classes of binary words, Sturmian words, \(\beta\)-shifts, and transcendence, Relation between powers of factors and the recurrence function characterizing Sturmian words, Words with the Maximum Number of Abelian Squares, A Square Root Map on Sturmian Words, Reversals and palindromes in continued fractions, On the structure and extendibility of \(k\)-power free words, Some combinatorial properties of Sturmian words, Abelian Repetitions in Sturmian Words, Lie complexity of words, Non-repetitive words: Ages and essences, On critical exponents in fixed points of non-erasing morphisms, On Sturmian graphs, On the conjugation of standard morphisms, Properties of infinite words : Recent results, Topological invariants for words of linear factor complexity, Sturmian words: structure, combinatorics, and their arithmetics, Sturmian words, Lyndon words and trees, Standard Sturmian morphisms, Abelian combinatorics on words: a survey, Fibonacci word patterns in two-way infinite Fibonacci words, Palindromes and Sturmian words, If a DOL language is k-power free then it is circular, Decimations and sturmian words, On Critical exponents in fixed points ofk-uniform binary morphisms, Thue type problems for graphs, points, and numbers, Frequencies of factors of Sturmian sequences, On a combinatorial property of Sturmian words, Generalized Sturmian languages, Generic continuous spectrum for ergodic Schrödinger operators, On the fixed points of the iterated pseudopalindromic closure operator, Note on powers in three interval exchange transformations, Fractional powers in Sturmian words, On powers of words occurring in binary codings of rotations, On \(\theta\)-episturmian words, Nombres réels de complexité sous-linéaire : mesures d'irrationalité et de transcendance, Unnamed Item, Sturmian words and words with a critical exponent, Aperiodic two-dimensional words of small abelian complexity, On the number of factors of Sturmian words, Characterization of repetitions in Sturmian words: a new proof, Studies on finite Sturmian words
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A permutational property of groups
- On the Burnside problem for semigroups
- On the subword complexity of DOL languages with a constant distribution
- An effective bound for groups of linear growth
- Rewriting products of group elements. I
- Permutation properties and the Fibonacci semigroup
- Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups
- On the factors of the Thue-Morse word on three symbols
- A combinatorial theorem on $p$-power-free words and an application to semigroups
- Uniform tag sequences
- Sequences with minimal block growth
