Refereed journal article or data article (A1)
On abelian saturated infinite words
List of Authors: Sergey Avgustinovich, Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina, Aleksi Saarela
Publisher: Elsevier
Publication year: 2019
Journal: Theoretical Computer Science
Journal name in source: Theoretical Computer Science
Volume number: 792
Start page: 154
End page: 160
ISSN: 0304-3975
eISSN: 1879-2294
DOI: http://dx.doi.org/10.1016/j.tcs.2018.05.013
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/31980994
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. |