TY - JOUR
AU - Juhani Karhumäki
AU - Aleksi Saarela
AU - Luca Q. Zamboni
PY - 2017/01/01
Y2 - 2020/08/04
TI - Variations of the Morse-Hedlund theorem for k-abelian equivalence
JF - Acta Cybernetica
JA - Acta Cybern
VL - 23
IS - 1
SE - Regular articles
DO - 10.14232/actacyb.23.1.2017.11
UR - https://cyber.bibl.u-szeged.hu/index.php/actcybern/article/view/3921
AB - In this paper we investigate local-to-global phenomena for a new family of complexity functions of infinite words indexed by k ≥ 0. Two finite words u and v are said to be k-abelian equivalent if for all words x 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, bridging the gap between the usual notion of abelian equivalence (when k = 1) and equality (when k = ∞). Given an infinite word w, we consider the associated complexity function 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.
ER -