Palindromes in circular words
Access Status
Fulltext not available
Authors
Simpson, Jamie
Date
2014Collection
Type
Journal Article
Metadata
Show full item recordAbstract
There is a very short and beautiful proof that the number of distinct nonempty 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 nonempty 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.
Citation
Simpson, J. 2014. Palindromes in circular words. Theoretical Computer Science. 550: pp. 6678.
Source Title
Theoretical Computer Science
Department
Department of Mathematics and Statistics
Related items
Showing items related by title, author, creator and subject.

Glen, A.; Simpson, Jamie (2013)A run in a word is a periodic factor whose length is at least twice its period and which cannot be extended to the left or right (by a letter) to a factor with greater period. In recent years a great deal of work has been ...

Barton, C.; Iliopoulos, Costas; Pissis, S. (2014)Background: Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist ...

Barton, C.; Iliopoulos, Costas; Pissis, S. (2014)Background: Circular string matching is a problem which naturally arises in many biological contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist ...