Palindromes in circular words
Simpson, J. (2014) Palindromes in circular words. Theoretical Computer Science, 550 . pp. 66-78.
*Subscription may be 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.
|Publication Type:||Journal Article|
|Murdoch Affiliation:||School of Engineering and Information Technology|
|Copyright:||© 2014 Elsevier Science B.V.|
|Item Control Page|