1. On k-abelian palindromes.
- Author
-
Cassaigne, Julien, Karhumäki, Juhani, and Puzynina, Svetlana
- Subjects
- *
ABELIAN equations , *ABELIAN functions , *ABELIAN groups , *GROUP theory , *BRAUER groups - Abstract
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 Θ ( n 2 ) distinct k -abelian palindromes as their factors. [ABSTRACT FROM AUTHOR]
- Published
- 2018
- Full Text
- View/download PDF