Abelian Combinatorics on Words: a Survey

Abstract

We survey known results and open problems in abelian combinatorics on words. Abelian combinatorics on words is the extension to the commutative setting of the classical theory of combinatorics on words. The extension is based on \emph{abelian equivalence}, which is the equivalence relation defined in the set of words by having the same Parikh vector, that is, the same number of occurrences of each letter of the alphabet. In the past few years, there was a lot of research on abelian analogues of classical definitions and properties in combinatorics on words. This survey aims to gather these results.

arXiv commentTo appear in Computer Science Review

References in corpus (15)

• Palindromic Richness
• Abelian Complexity in Minimal Subshifts
• Balance and Abelian complexity of the Tribonacci word
• Anti-Powers in Infinite Words
• Infinite Self-Shuffling Words
• Abelian-Square-Rich Words
• Abelian powers in paper-folding words
• Abelian maximal pattern complexity of words
• Abelian complexity function of the Tribonacci word
• Avoiding abelian powers cyclically
• On $k$-abelian Equivalence and Generalized Lagrange Spectra
• Abelian periods of factors of Sturmian words
• Abelian Complexity and Synchronization
• On Abelian Closures of Infinite Non-binary Words
• Solved and unsolved problems about abelian squares