A4 Refereed article in a conference publication
On k-abelian palindromic rich and poor words
Authors: Karhumäki J., Puzynina S.
Editors: Arseny M. Shur, Mikhail V. Volkov
Conference name: Developments in Language Theory
Publisher: Springer Verlag
Publication year: 2014
Book title : Developments in Language Theory
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Lecture Notes in Computer Science
Number in series: 8633
First page : 191
Last page: 202
ISBN: 978-3-319-09697-1
eISBN: 978-3-319-09698-8
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-319-09698-8_17
Web address : http://api.elsevier.com/content/abstract/scopus_id:84906495395
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. It is easy to see that there are no abelian poor words, and there exist words containing Θ(n ) distinct abelian palindromes. We analyze these notions with respect to k-abelian equivalence. We show that in the k-abelian case there exist poor words containing finitely many distinct k-abelian palindromic factors, and there exist rich words containing Θ(n ) distinct k-abelian palindromes as their factors. Therefore, for poor words the situation resembles normal words, while for rich words it is similar to the abelian case. © 2014 Springer International Publishing Switzerland.