Abelian complexity of minimal subshifts
From MaRDI portal
Publication:3074533
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
(64)- Abelian combinatorics on words: a survey
- Avoiding three consecutive blocks of the same size and same sum
- Properties of a ternary infinite word
- On balanced and abelian properties of circular words over a ternary alphabet
- On abelian and additive complexity in infinite words
- Weighted prefix normal words: mind the gap
- Abelian periods of factors of Sturmian words
- Aperiodic two-dimensional words of small abelian complexity
- Separating the words of a language by counting factors
- On the asymptotic abelian complexity of morphic words
- Abelian closures of infinite binary words
- On the additive complexity of a Thue-Morse-like sequence
- Computing abelian complexity of binary uniform morphic words
- On abelian subshifts
- On the boundary sequence of an automatic sequence
- A note on abelian returns in rotation words
- Abelian powers and repetitions in Sturmian words
- Open and closed factors in Arnoux-Rauzy words
- Regularity of aperiodic minimal subshifts
- scientific article; zbMATH DE number 6272378 (Why is no real title available?)
- Abelian maximal pattern complexity of words
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Abelian antipowers in infinite words
- Abelian complexity and frequencies of letters in infinite words
- On the abelian complexity of generalized Thue-Morse sequences
- On k-abelian palindromes
- Sturmian jungle (or garden?) On multiliteral alphabets
- Eulerian entropy and non-repetitive subword complexity
- scientific article; zbMATH DE number 7559450 (Why is no real title available?)
- Abelian-square-rich words
- The Frobenius problem for homomorphic embeddings of languages into the integers
- On the abelian complexity of the Rudin-Shapiro sequence
- On infinite prefix normal words
- Cyclic Complexity of Words
- Subword complexity and power avoidance
- Cototal enumeration degrees and their applications to effective mathematics
- Minimal Complexities for Infinite Words Written with d Letters
- Abelian repetitions in Sturmian words
- Characterizations of families of morphisms and words via binomial complexities
- The abelian complexity of infinite words and the Frobenius problem
- Abelian properties of Parry words
- On a Class of 2-Balanced Sequences
- Abelian complexity of infinite words associated with quadratic Parry numbers
- On \(k\)-abelian equivalence and generalized Lagrange spectra
- Another generalization of abelian equivalence: binomial complexity of infinite words
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- Abelian bordered factors and periodicity
- Relations on words
- 2-balanced sequences coding rectangle exchange transformation
- On the k-abelian complexity of the Cantor sequence
- Abelian complexity and synchronization
- On the 2-abelian complexity of generalized Cantor sequences
- Cyclic complexity of words
- On abelian versions of critical factorization theorem
- On the 2-binomial complexity of the generalized Thue-Morse words
- A square root map on Sturmian words
- Lie complexity of words
- On a generalization of abelian equivalence and complexity of infinite words
- A characterization of subshifts with bounded powers
- Balances and Abelian complexity of a certain class of infinite ternary words
- Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
- On a group theoretic generalization of the Morse-Hedlund theorem
- Abelian complexity and abelian co-decomposition
- Recurrent words with constant abelian complexity
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)
