Abstract: In this paper we undertake the general study of the Abelian complexity of an infinite word on a finite alphabet. We investigate both similarities and differences between the Abelian complexity and the usual subword complexity. While the Thue-Morse minimal subshift is neither characterized by its Abelian complexity nor by its subword complexity alone, we show that the subshift is completely characterized by the two complexity functions together. We give an affirmative answer to an old question of G. Rauzy by exhibiting a class of words whose Abelian complexity is everywhere equal to 3. We also investigate links between Abelian complexity and the existence of Abelian powers. Using van der Waerden's Theorem, we show that any minimal subshift having bounded Abelian complexity contains Abelian k-powers for every positive integer k. In the case of Sturmian words we prove something stronger: For every Sturmian word w and positive integer k, each sufficiently long factor of w begins in an Abelian k-power.
Recommendations
Cited in
(69)- On abelian subshifts
- Regularity of aperiodic minimal subshifts
- The Frobenius problem for homomorphic embeddings of languages into the integers
- On the k-abelian complexity of the Cantor sequence
- On the additive complexity of a Thue-Morse-like sequence
- On k-abelian palindromes
- Abelian complexity and abelian co-decomposition
- Abelian antipowers in infinite words
- On the 2-abelian complexity of generalized Cantor sequences
- On balanced and abelian properties of circular words over a ternary alphabet
- Lie complexity of words
- Abelian periods of factors of Sturmian words
- On the boundary sequence of an automatic sequence
- Abelian closures of infinite binary words
- Subword complexity and power avoidance
- Aperiodic two-dimensional words of small abelian complexity
- Abelian-square-rich words
- On the asymptotic abelian complexity of morphic words
- On the abelian complexity of the Rudin-Shapiro sequence
- On the abelian complexity of generalized Thue-Morse sequences
- Open and closed factors in Arnoux-Rauzy words
- A note on abelian returns in rotation words
- Computing abelian complexity of binary uniform morphic words
- Abelian complexity and frequencies of letters in infinite words
- Abelian powers and repetitions in Sturmian words
- On abelian versions of critical factorization theorem
- Cyclic Complexity of Words
- Sturmian jungle (or garden?) On multiliteral alphabets
- Balances and Abelian complexity of a certain class of infinite ternary words
- Avoiding three consecutive blocks of the same size and same sum
- On \(k\)-abelian equivalence and generalized Lagrange spectra
- On a generalization of abelian equivalence and complexity of infinite words
- A characterization of subshifts with bounded powers
- Cototal enumeration degrees and their applications to effective mathematics
- On abelian and additive complexity in infinite words
- Abelian properties of Parry words
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Abelian complexity and synchronization
- The abelian complexity of infinite words and the Frobenius problem
- Abelian bordered factors and periodicity
- Relations on words
- Cyclic complexity of words
- scientific article; zbMATH DE number 7559450 (Why is no real title available?)
- Separating the words of a language by counting factors
- Abelian maximal pattern complexity of words
- A square root map on Sturmian words
- On a group theoretic generalization of the Morse-Hedlund theorem
- Abelian repetitions in Sturmian words
- scientific article; zbMATH DE number 6272378 (Why is no real title available?)
- Recurrent words with constant abelian complexity
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- On infinite prefix normal words
- Properties of a ternary infinite word
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- Abelian combinatorics on words: a survey
- Minimal Complexities for Infinite Words Written with d Letters
- On a Class of 2-Balanced Sequences
- On the 2-binomial complexity of the generalized Thue-Morse words
- Characterizations of families of morphisms and words via binomial complexities
- Abelian complexity of infinite words associated with quadratic Parry numbers
- Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
- 2-balanced sequences coding rectangle exchange transformation
- Weighted prefix normal words
- Complexity of infinite words
- A dynamical view of Tijdeman's solution of the chairman assignment problem
- \(N\)-factor complexity of the Fibonacci sequence on \(\mathbb{N}\) and the factor-counting sequences
- Additive word complexity and \texttt{Walnut}
- Eulerian entropy and non-repetitive subword complexity
- Weighted prefix normal words: mind the gap
This page was built for publication: Abelian complexity of minimal subshifts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3074533)
