On abelian saturated infinite words

On abelian saturated infinite words Full article

Journal

Theoretical Computer Science
ISSN: 0304-3975

Output data

Year: 2019, Volume: 792, Pages: 154-160 Pages count : 7 DOI: 10.1016/j.tcs.2018.05.013

Tags

Abelian equivalence; Combinatorics on words; Palindrome; Rich word

Authors

Avgustinovich Sergey ¹ , Cassaigne Julien ² , Karhumäki Juhani ³ , Puzynina Svetlana ^4,1 , Saarela Aleksi ³

Affiliations

1	Sobolev Institute of Mathematics, Russia
2	Institut de Mathématiques de Marseille, Case 907, 13288 Marseille Cedex 9, France
3	Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland
4	St. Petersburg State University, 14th Line V.O., 29B, Saint Petersburg, 199178, Russia

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 \Theta(f (n)) abelian nonequivalent factors. We show that binary infinite words cannot be abelian n^2-saturated, but, for any ε > 0, they can be abelian n^{2-ε}-saturated. There is also a sequence of finite words (w_n), with |w_n| = n, such that each w_n contains at least Cn^2 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.

Avgustinovich S. , Cassaigne J. , Karhumäki J. , Puzynina S. , Saarela A.
On abelian saturated infinite words
Theoretical Computer Science. 2019. V.792. P.154-160. DOI: 10.1016/j.tcs.2018.05.013 WOS Scopus РИНЦ OpenAlex

Submitted:	Jan 18, 2018
Accepted:	May 10, 2018
Published print:	Nov 5, 2019

Web of science:	WOS:000490648500012
Scopus:	2-s2.0-85047205785
Elibrary:	41782257
OpenAlex:	W2803511783

DB	Citing
Elibrary	3
Scopus	3
Web of science	3
OpenAlex	4