A1 Journal article – refereed

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

List of Authors: Karhumaki J, Saarela A, Zamboni LQ


Publication year: 2017

Journal: Acta Cybernetica

Journal name in source: ACTA CYBERNETICA

Journal acronym: ACTA CYBERN

Volume number: 23

Issue number: 1

Number of pages: 15

ISSN: 0324-721X

DOI: http://dx.doi.org/10.14232/actacyb.23.1.2017.11

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 = infinity). 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.

Downloadable publication

This is an electronic reprint of the original article.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.

Last updated on 2021-24-06 at 08:50