Palindromes in circular words
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...
| Main Author: | |
|---|---|
| Format: | Journal Article |
| Published: |
Elsevier
2014
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/26621 |
| _version_ | 1848752038286983168 |
|---|---|
| author | Simpson, Jamie |
| author_facet | Simpson, Jamie |
| author_sort | Simpson, Jamie |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | 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. |
| first_indexed | 2025-11-14T08:02:16Z |
| format | Journal Article |
| id | curtin-20.500.11937-26621 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T08:02:16Z |
| publishDate | 2014 |
| publisher | Elsevier |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-266212017-09-13T15:53:51Z Palindromes in circular words Simpson, Jamie Palindromes Circular words 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. 2014 Journal Article http://hdl.handle.net/20.500.11937/26621 10.1016/j.tcs.2014.07.012 Elsevier restricted |
| spellingShingle | Palindromes Circular words Simpson, Jamie Palindromes in circular words |
| title | Palindromes in circular words |
| title_full | Palindromes in circular words |
| title_fullStr | Palindromes in circular words |
| title_full_unstemmed | Palindromes in circular words |
| title_short | Palindromes in circular words |
| title_sort | palindromes in circular words |
| topic | Palindromes Circular words |
| url | http://hdl.handle.net/20.500.11937/26621 |