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 2) 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 2) 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.

Original languageEnglish
Title of host publicationDevelopments in Language Theory - 18th International Conference, DLT 2014, Proceedings
PublisherSpringer Nature
Pages191-202
Number of pages12
ISBN (Print)9783319096971
DOIs
StatePublished - 1 Jan 2014
Event18th International Conference on Developments in Language Theory, DLT 2014 - Ekaterinburg, Russian Federation
Duration: 26 Aug 201429 Aug 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8633 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference on Developments in Language Theory, DLT 2014
Country/TerritoryRussian Federation
CityEkaterinburg
Period26/08/1429/08/14

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41130063