Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование
A word is called a palindrome if it is equal to its reversal. In the paper we consider a k-abelian modification of this notion. Two words are called k-abelian equivalent if they contain the same number of occurrences of each factor of length at most k. We say that a word is a k-abelian palindrome if it is k-abelian equivalent to its reversal. A question we deal with is the following: how many distinct palindromes can a word contain? It is well known that a word of length n can contain at most n+1 distinct palindromes as its factors; such words are called rich. On the other hand, there exist infinite words containing only finitely many distinct palindromes as their factors; such words are called poor. We show that in the k-abelian case there exist infinite words containing finitely many distinct k-abelian palindromic factors. For rich words we show that there exist finite words of length n containing Θ(n2) distinct k-abelian palindromes as their factors.
| Язык оригинала | английский |
|---|---|
| Страницы (с-по) | 89-98 |
| Число страниц | 10 |
| Журнал | Information and Computation |
| Том | 260 |
| DOI | |
| Состояние | Опубликовано - 1 июн 2018 |
ID: 35280900