A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä

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

Julkaisun tekijät: Karhumaki J, Saarela A, Zamboni LQ


Julkaisuvuosi: 2017

Journal: Acta Cybernetica

Tietokannassa oleva lehden nimi: ACTA CYBERNETICA

Lehden akronyymi: ACTA CYBERN

Volyymi: 23

Julkaisunumero: 1

Sivujen määrä: 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.

Ladattava julkaisu

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