On the number of palindromically rich words
Glen, A.ORCID: 0000-0002-9434-3412
(2015)
On the number of palindromically rich words.
In: 59th Annual Meeting of the Australian Mathematical Society, 28 September - 1 October 2015, Flinders University, Adelaide.
Abstract
Rich words (also known as full words ) are a special family of finite and infinite words characterised by containing the maximal number of distinct palindromes. We prove that the number of rich words of length n over a finite alphabet A (consisting of 3 or more letters) grows at least polynomially with the size of A. We also show asymptotic exponential growth for the number of rich words of length 2n over a 2-letter alphabet. Moreover, we discuss possible factor complexity functions of rich words and consider the difficult (open) problem of enumerating the finite rich words over a fixed finite alphabet.
Item Type: | Conference Item |
---|---|
Murdoch Affiliation(s): | School of Engineering and Information Technology |
Conference Website: | https://www.austms.org.au/ |
URI: | http://researchrepository.murdoch.edu.au/id/eprint/39771 |
![]() |
Item Control Page |
Downloads
Downloads per month over past year