Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Palindromes in circular words

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

[img]
Preview
PDF - Published Version
Download (318kB) | Preview
Free to read: http://dx.doi.org/10.1016/j.tcs.2014.07.012
*No subscription 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.

Item 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

Downloads

Downloads per month over past year