×

Variations of the Morse-Hedlund theorem for \(k\)-abelian equivalence. (English) Zbl 1389.68063

Summary: In this paper we investigate local-to-global phenomena for a new family of complexity functions of infinite words indexed by \(k \geq 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 = \infty\)). 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.

MSC:

68R15 Combinatorics on words
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI