TY - JOUR

T1 - On k-abelian palindromes

AU - Cassaigne, Julien

AU - Karhumäki, Juhani

AU - Puzynina, Svetlana

PY - 2018/6/1

Y1 - 2018/6/1

N2 - 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.

AB - 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.

KW - Infinite words

KW - k-Abelian equivalence

KW - Palindromes

KW - Rich words

KW - THEOREM

KW - COMPLEXITY

KW - STURMIAN WORDS

KW - INFINITE WORDS

UR - http://www.scopus.com/inward/record.url?scp=85045541682&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2018.04.001

DO - 10.1016/j.ic.2018.04.001

M3 - Article

AN - SCOPUS:85045541682

VL - 260

SP - 89

EP - 98

JO - Information and Computation

JF - Information and Computation

SN - 0890-5401

ER -