A1 Journal article – refereed
On abelian saturated infinite words




List of Authors: Sergey Avgustinovich, Julien Cassaigne, Juhani Karhumäki, Svetlana Puzynina, Aleksi Saarela
Publisher: Elsevier
Publication year: 2018
Journal: Theoretical Computer Science
Journal name in source: Theoretical Computer Science
ISSN: 0304-3975
eISSN: 1879-2294

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 2019-07-02 at 14:31