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