Catalog Home Page

Palindromes in circular words

Simpson, J. (2014) Palindromes in circular words. Theoretical Computer Science, 550 . pp. 66-78.

PDF - Published Version
Download (318kB) | Preview
Free to read:
*No subscription required


There is a very short and beautiful proof that the number of distinct non-empty palindromes in a word of length n is at most n. In this paper we show, with a very complicated proof, that the number of distinct non-empty palindromes with length at most n in a circular word of length n is less than 5n/3. For n divisible by 3 we present circular words of length n containing 5n/3-2 distinct palindromes, so the bound is almost sharp. The paper finishes with some open problems.

Item Type: Journal Article
Murdoch Affiliation: School of Engineering and Information Technology
Publisher: Elsevier BV
Copyright: © 2014 Elsevier Science B.V.
Item Control Page Item Control Page


Downloads per month over past year