On a generalization of Abelian equivalence and complexity of infinite words
Juhani Karhumäki, Aleksi Saarela, Luca Quardo Zamboni · UTUPub (University of Turku) · 2013
In this paper we introduce and study a family of complexity functions of infinite words indexed by $k \in \ints ^+ \cup {+\infty}.$ Let $k \in \ints ^+ \cup {+\infty}$ and $A$ be a finite non-empty set. Two finite words $u$ and $v$ in $A^*$ are said to be $k$-Abelian equivalent if for all $x\in A^*$ 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 $\thicksim_k$ on $A^*,$ bridging the gap between the usual notion of Abelian equivalence (when $k=1$) and equality (when $k=+\infty).$ We show that the number of $k$-Abelian equivalence classes of words of length $n$ grows polynomially, although the degree is exponential in $k.$ Given an infinite word $ω\in A^ ats,$ we consider the associated complexity function $\mathcal {P}^{(k)}_ω: ats \rightarrow ats$ which counts the number of $k$-Abelian equivalence classes of factors of $ω$ of length $n.$ We show that the complexity function $\mathcal {P}^{(k)}$ is intimately linked with periodicity. More precisely we define an auxiliary function $q^k: ats \rightarrow ats$ and show that if $\mathcal {P}^{(k)}_ω(n)