A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

On abelian saturated infinite words




TekijätSergey Avgustinovich, Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina, Aleksi Saarela

KustantajaElsevier

Julkaisuvuosi2019

JournalTheoretical Computer Science

Tietokannassa oleva lehden nimiTheoretical Computer Science

Vuosikerta792

Aloitussivu154

Lopetussivu160

ISSN0304-3975

eISSN1879-2294

DOIhttps://doi.org/10.1016/j.tcs.2018.05.013

Rinnakkaistallenteen osoitehttps://research.utu.fi/converis/portal/detail/Publication/31980994


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 2024-26-11 at 16:29