A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
On a generalization of Abelian equivalence and complexity of infinite words
Tekijät: Juhani Karhumaki, Aleksi Saarela, Luca Q Zamboni
Kustantaja: ACADEMIC PRESS INC ELSEVIER SCIENCE
Julkaisuvuosi: 2013
Journal: Journal of Combinatorial Theory, Series A
Tietokannassa oleva lehden nimi: JOURNAL OF COMBINATORIAL THEORY SERIES A
Lehden akronyymi: J COMB THEORY A
Numero sarjassa: 8
Vuosikerta: 120
Numero: 8
Aloitussivu: 2189
Lopetussivu: 2206
Sivujen määrä: 18
ISSN: 0097-3165
DOI: https://doi.org/10.1016/j.jcta.2013.08.008
Tiivistelmä
In this paper we introduce and study a family of complexity functions of infinite words indexed by k in Z^+ U {+infinity}. Let k in Z^+ U {+infinity} and A be a finite non-empty set. Two finite words u and v in A* are said to be k-Abelian equivalent if for all x in A* 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 sim_k on A*, bridging the gap between the usual notion of Abelian equivalence (when k = 1) and equality (when k = +infinity). We show that the number of k-Abelian equivalence classes of words of length n grows polynomially, although the degree is exponential in k. Given an infinite word omega in A^N, we consider the associated complexity function P^(k)_omega : N -> N which counts the number of k-Abelian equivalence classes of factors of omega of length n. We show that the complexity function P_k is intimately linked with periodicity. More precisely we define an auxiliary function q^k : N -> N and show that if P^(k)_omega(n) < q^k(n) for some k in Z^+ U {+infinity} and n >= 0, then omega is ultimately periodic. Moreover if omega is aperiodic, then P^(k)_omega(n) = q^k(n) if and only if omega is Sturmian. We also study k-Abelian complexity in connection with repetitions in words. Using Szemeredi's theorem, we show that if omega has bounded k-Abelian complexity, then for every D subset of N with positive upper density and for every positive integer N, there exists a k-Abelian N-power occurring in omega at some position j in D.
In this paper we introduce and study a family of complexity functions of infinite words indexed by k in Z^+ U {+infinity}. Let k in Z^+ U {+infinity} and A be a finite non-empty set. Two finite words u and v in A* are said to be k-Abelian equivalent if for all x in A* 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 sim_k on A*, bridging the gap between the usual notion of Abelian equivalence (when k = 1) and equality (when k = +infinity). We show that the number of k-Abelian equivalence classes of words of length n grows polynomially, although the degree is exponential in k. Given an infinite word omega in A^N, we consider the associated complexity function P^(k)_omega : N -> N which counts the number of k-Abelian equivalence classes of factors of omega of length n. We show that the complexity function P_k is intimately linked with periodicity. More precisely we define an auxiliary function q^k : N -> N and show that if P^(k)_omega(n) < q^k(n) for some k in Z^+ U {+infinity} and n >= 0, then omega is ultimately periodic. Moreover if omega is aperiodic, then P^(k)_omega(n) = q^k(n) if and only if omega is Sturmian. We also study k-Abelian complexity in connection with repetitions in words. Using Szemeredi's theorem, we show that if omega has bounded k-Abelian complexity, then for every D subset of N with positive upper density and for every positive integer N, there exists a k-Abelian N-power occurring in omega at some position j in D.
Ladattava julkaisu This is an electronic reprint of the original article. |  |
Turun yliopiston Tutkimustietojärjestelmän portaali