A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
On abelian saturated infinite words




Julkaisun tekijät: Sergey Avgustinovich, Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina, Aleksi Saarela
Kustantaja: Elsevier
Julkaisuvuosi: 2018
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: Theoretical Computer Science
ISSN: 0304-3975
eISSN: 1879-2294

Tiivistelmä

Let f:Z+→R be an increasing function. We say that an infinite word w is abelian f(n)-saturated if each factor of length n contains Θ(f(n)) abelian nonequivalent factors. We show that binary infinite words cannot be abelian n2-saturated, but, for any ε>0, they can be abelian n2−ε-saturated. There is also a sequence of finite words (wn), with |wn|=n, such that each wn contains at least Cn2 abelian nonequivalent factors for some constant C>0. We also consider saturated words and their connection to palindromic richness in the case of equality and k-abelian equivalence.


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 2019-02-07 at 17:46