Journal article
Palindromes in circular words
Theoretical Computer Science, Vol.550, pp.66-78
2014
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.
Details
- Title
- Palindromes in circular words
- Authors/Creators
- J. Simpson (Author/Creator) - Murdoch University
- Publication Details
- Theoretical Computer Science, Vol.550, pp.66-78
- Publisher
- Elsevier BV
- Identifiers
- 991005543823107891
- Copyright
- © 2014 Elsevier Science B.V.
- Murdoch Affiliation
- School of Engineering and Information Technology
- Language
- English
- Resource Type
- Journal article
Metrics
74 File views/ downloads
33 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- Citation topics
- 9 Mathematics
- 9.28 Pure Maths
- 9.28.534 Dynamical Systems
- Web Of Science research areas
- Computer Science, Theory & Methods
- ESI research areas
- Computer Science