Variations of the Morse-Hedlund Theorem for $k$-Abelian Equivalence

Abstract

In this paper we investigate local to global phenomena for a new family of complexity functions of infinite words indexed by $k \in \Ni \cup \{+\infty\}$ where $\Ni$ denotes the set of positive integers. Two finite words $u$ and $v$ in $A^{\ast }$ are said to be $k$-Abelian equivalent if for all $x\in A^{\ast }$ of length less than or equal to $k$, the number of occurrences of $x$ in $u$ is equal to the number of occurrences of $x$ in $v$. This defines a family of equivalence relations ${\sim }_k$ on $A^{\ast }$, bridging the gap between the usual notion of Abelian equivalence (when $k=1$) and equality (when $k=+\infty$). Given an infinite word $w\in A^{\omega }$, we consider the associated complexity function $\mathcal P^{(k)}_w : \Ni \rightarrow \Ni$ which counts the number of $k$-Abelian equivalence classes of factors of $w$ of length $n$. As a whole, these complexity functions have a number of common features: Each gives a characterization of periodicity in the context of bi-infinite words, and each can be used to characterize Sturmian words in the framework of aperiodic one-sided infinite words. Nevertheless, they also exhibit a number of striking differences, the study of which is one of the main topics of our paper.

Cited by in corpus (1)

• On the 2-Abelian Complexity of the Thue-Morse Word