Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
On k-abelian palindromic rich and poor words. / Karhumäki, Juhani; Puzynina, Svetlana.
Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings. Springer Nature, 2014. p. 191-202 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8633 LNCS).Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
}
TY - GEN
T1 - On k-abelian palindromic rich and poor words
AU - Karhumäki, Juhani
AU - Puzynina, Svetlana
PY - 2014/1/1
Y1 - 2014/1/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. 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.
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. 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.
UR - http://www.scopus.com/inward/record.url?scp=84958533383&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-09698-8_17
DO - 10.1007/978-3-319-09698-8_17
M3 - Conference contribution
AN - SCOPUS:84958533383
SN - 9783319096971
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 191
EP - 202
BT - Developments in Language Theory - 18th International Conference, DLT 2014, Proceedings
PB - Springer Nature
T2 - 18th International Conference on Developments in Language Theory, DLT 2014
Y2 - 26 August 2014 through 29 August 2014
ER -
ID: 41130063