Palindromes in circular words
dc.contributor.author | Simpson, Jamie | |
dc.date.accessioned | 2017-01-30T12:54:22Z | |
dc.date.available | 2017-01-30T12:54:22Z | |
dc.date.created | 2015-05-22T08:32:23Z | |
dc.date.issued | 2014 | |
dc.identifier.citation | Simpson, J. 2014. Palindromes in circular words. Theoretical Computer Science. 550: pp. 66-78. | |
dc.identifier.uri | http://hdl.handle.net/20.500.11937/26621 | |
dc.identifier.doi | 10.1016/j.tcs.2014.07.012 | |
dc.description.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. | |
dc.publisher | Elsevier | |
dc.subject | Palindromes | |
dc.subject | Circular words | |
dc.title | Palindromes in circular words | |
dc.type | Journal Article | |
dcterms.source.volume | 550 | |
dcterms.source.startPage | 66 | |
dcterms.source.endPage | 78 | |
dcterms.source.issn | 0304-3975 | |
dcterms.source.title | Theoretical Computer Science | |
curtin.department | Department of Mathematics and Statistics | |
curtin.accessStatus | Fulltext not available |