  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^*$ 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 $\sim_k$ on $A^*$, 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.
