Abelian complexity of minimal subshifts
From MaRDI portal
Publication:3074533
DOI10.1112/JLMS/JDQ063zbMATH Open1211.68300arXiv0911.2914OpenAlexW3105514554MaRDI QIDQ3074533FDOQ3074533
Authors: Gwénaël Richomme, Kalle Saari, Luca Q. Zamboni 
Publication date: 9 February 2011
Published in: Journal of the London Mathematical Society (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/0911.2914
Recommendations
Cited In (60)
- Characterizations of families of morphisms and words via binomial complexities
- The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
- 2-balanced sequences coding rectangle exchange transformation
- On the 2-binomial complexity of the generalized Thue-Morse words
- Proof of a conjecture of Krawchuk and Rampersad on the cyclic complexity of the Thue-Morse sequence
- On $k$-abelian equivalence and generalized Lagrange spectra
- On abelian and additive complexity in infinite words
- On balanced and abelian properties of circular words over a ternary alphabet
- Abelian periods of factors of Sturmian words
- Aperiodic two-dimensional words of small abelian complexity
- Weighted prefix normal words: mind the gap
- 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 the boundary sequence of an automatic sequence
- A note on abelian returns in rotation words
- Title not available (Why is that?)
- Computing the \(k\)-binomial complexity of the Thue-Morse word
- Abelian maximal pattern complexity of words
- Open and closed factors in Arnoux-Rauzy words
- Abelian powers and repetitions in Sturmian words
- Abelian complexity and frequencies of letters in infinite words
- Abelian Repetitions in Sturmian Words
- Abelian antipowers in infinite words
- On the abelian complexity of generalized Thue-Morse sequences
- On \(k\)-abelian palindromes
- Title not available (Why is that?)
- Sturmian jungle (or garden?) On multiliteral alphabets
- Eulerian entropy and non-repetitive subword complexity
- Avoiding Three Consecutive Blocks of the Same Size and Same Sum
- 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
- Abelian Complexity and Synchronization
- Cyclic Complexity of Words
- Cototal enumeration degrees and their applications to effective mathematics
- Minimal Complexities for Infinite Words Written with d Letters
- The abelian complexity of infinite words and the Frobenius problem
- On a Class of 2-Balanced Sequences
- Abelian properties of Parry words
- Separating the Words of a Language by Counting Factors
- Abelian complexity of infinite words associated with quadratic Parry numbers
- Another generalization of abelian equivalence: binomial complexity of infinite words
- Abelian bordered factors and periodicity
- Relations on words
- Weak abelian periodicity of infinite words
- On the \(k\)-abelian complexity of the Cantor sequence
- On the 2-abelian complexity of generalized Cantor sequences
- On abelian versions of critical factorization theorem
- Cyclic complexity of words
- A square root map on Sturmian words
- Lie complexity of words
- Balances and Abelian complexity of a certain class of infinite ternary words
- On a group theoretic generalization of the Morse-Hedlund theorem
- On a generalization of abelian equivalence and complexity of infinite words
- Abelian complexity and abelian co-decomposition
- Abelian combinatorics on words: a survey
- Properties of a ternary infinite word
- 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)
