A1 Refereed original research article in a scientific journal
Variations of the Morse-Hedlund Theorem for k-Abelian Equivalence
Authors: Karhumaki J, Saarela A, Zamboni LQ
Publisher: UNIV SZEGED, FAC SCIENCE
Publication year: 2017
Journal: Acta Cybernetica
Journal name in source: ACTA CYBERNETICA
Journal acronym: ACTA CYBERN
Volume: 23
Issue: 1
First page : 175
Last page: 189
Number of pages: 15
ISSN: 0324-721X
DOI: https://doi.org/10.14232/actacyb.23.1.2017.11
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/25896377
Abstract
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.
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. |  |
UTU Research Portal