On abelian saturated infinite words | Sciact - Система учета научной деятельности ИМ СО РАН

On abelian saturated infinite words Научная публикация

Журнал

Theoretical Computer Science
ISSN: 0304-3975

Вых. Данные

Год: 2019, Том: 792, Страницы: 154-160 Страниц : 7 DOI: 10.1016/j.tcs.2018.05.013

Ключевые слова

Abelian equivalence; Combinatorics on words; Palindrome; Rich word

Авторы

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

Организации

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

Поступила в редакцию:	18 янв. 2018 г.
Принята к публикации:	10 мая 2018 г.
Опубликована в печати:	5 нояб. 2019 г.

Web of science:	WOS:000490648500012
Scopus:	2-s2.0-85047205785
РИНЦ:	41782257
OpenAlex:	W2803511783

БД	Цитирований
РИНЦ	3
Scopus	3
Web of science	3
OpenAlex	4