Standard

On abelian saturated infinite words. / Avgustinovich, Sergey; Cassaigne, Julien; Karhumäki, Juhani; Puzynina, Svetlana; Saarela, Aleksi.

в: Theoretical Computer Science, Том 792, 05.11.2019, стр. 154-160.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Avgustinovich, S, Cassaigne, J, Karhumäki, J, Puzynina, S & Saarela, A 2019, 'On abelian saturated infinite words', Theoretical Computer Science, Том. 792, стр. 154-160. https://doi.org/10.1016/j.tcs.2018.05.013

APA

Avgustinovich, S., Cassaigne, J., Karhumäki, J., Puzynina, S., & Saarela, A. (2019). On abelian saturated infinite words. Theoretical Computer Science, 792, 154-160. https://doi.org/10.1016/j.tcs.2018.05.013

Vancouver

Avgustinovich S, Cassaigne J, Karhumäki J, Puzynina S, Saarela A. On abelian saturated infinite words. Theoretical Computer Science. 2019 Нояб. 5;792:154-160. https://doi.org/10.1016/j.tcs.2018.05.013

Author

Avgustinovich, Sergey ; Cassaigne, Julien ; Karhumäki, Juhani ; Puzynina, Svetlana ; Saarela, Aleksi. / On abelian saturated infinite words. в: Theoretical Computer Science. 2019 ; Том 792. стр. 154-160.

BibTeX

@article{684e3d7b2a544a22810049fa21b52cb2,
title = "On abelian saturated infinite words",
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.",
keywords = "Abelian equivalence, Combinatorics on words, Palindrome, Rich word",
author = "Sergey Avgustinovich and Julien Cassaigne and Juhani Karhum{\"a}ki and Svetlana Puzynina and Aleksi Saarela",
year = "2019",
month = nov,
day = "5",
doi = "10.1016/j.tcs.2018.05.013",
language = "English",
volume = "792",
pages = "154--160",
journal = "Theoretical Computer Science",
issn = "0304-3975",
publisher = "Elsevier",

}

RIS

TY - JOUR

T1 - On abelian saturated infinite words

AU - Avgustinovich, Sergey

AU - Cassaigne, Julien

AU - Karhumäki, Juhani

AU - Puzynina, Svetlana

AU - Saarela, Aleksi

PY - 2019/11/5

Y1 - 2019/11/5

N2 - 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.

AB - 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.

KW - Abelian equivalence

KW - Combinatorics on words

KW - Palindrome

KW - Rich word

UR - http://www.scopus.com/inward/record.url?scp=85047205785&partnerID=8YFLogxK

UR - http://www.mendeley.com/research/abelian-saturated-infinite-words

U2 - 10.1016/j.tcs.2018.05.013

DO - 10.1016/j.tcs.2018.05.013

M3 - Article

AN - SCOPUS:85047205785

VL - 792

SP - 154

EP - 160

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

ER -

ID: 35281074