A1 Refereed original research article in a scientific journal

On abelian saturated infinite words




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

PublisherElsevier

Publication year2019

JournalTheoretical Computer Science

Journal name in sourceTheoretical Computer Science

Volume792

First page 154

Last page160

ISSN0304-3975

eISSN1879-2294

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