Catalog Home Page

Palindromes in circular words

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

Link to Published Version: http://dx.doi.org/10.1016/j.tcs.2014.07.012
*Subscription may be required

Abstract

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
Publisher: Elsevier BV
Copyright: © 2014 Elsevier Science B.V.
URI: http://researchrepository.murdoch.edu.au/id/eprint/23296
Item Control Page Item Control Page