Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4950953 | Information Processing Letters | 2016 | 4 Pages |
Abstract
A length n word is (palindromic) rich if it contains the maximum possible number, which is n, of distinct non-empty palindromic factors. We prove both necessary and sufficient conditions for richness in terms of run-length encodings of words. Relating sufficient conditions to integer partitions, we prove a lower bound of order Cn, where Câ37.6, on the growth function of the language of binary rich words. From experimental study we suggest that this growth function actually grows more slowly than nn, which makes our lower bound quite reasonable.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Chuan Guo, Jeffrey Shallit, Arseny M. Shur,