Refereed journal article or data article (A1)

On abelian saturated infinite words




List of AuthorsSergey Avgustinovich, Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina, Aleksi Saarela

PublisherElsevier

Publication year2019

JournalTheoretical Computer Science

Journal name in sourceTheoretical Computer Science

Volume number792

Start page154

End page160

ISSN0304-3975

eISSN1879-2294

DOIhttp://dx.doi.org/10.1016/j.tcs.2018.05.013

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/31980994


Abstract

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.


Downloadable publication

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 2022-07-04 at 16:55