A1 Refereed original research article in a scientific journal

On k-abelian palindromes




AuthorsJulien Cassaigne, Juhani Karhumäki, Svetlana Puzynina

PublisherElsevier Inc.

Publication year2018

JournalInformation and Computation

Journal name in sourceInformation and Computation

Volume260

First page 89

Last page98

Number of pages10

ISSN0890-5401

eISSN1090-2651

DOIhttps://doi.org/10.1016/j.ic.2018.04.001


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 Θ(n2)

distinct k-abelian palindromes as their factors.



Last updated on 2024-26-11 at 12:16