Smallest and Largest Block Palindrome Factorizations
share
A palindrome is a word that reads the same forwards and backwards. A block palindrome factorization (or BP-factorization) is a factorization of a word into blocks that becomes palindrome if each identical block is replaced by a distinct symbol. We call the number of blocks in a BP-factorization the width of the BP-factorization. The largest BP-factorization of a word w is the BP-factorization of w with the maximum width. We study words with certain BP-factorizations. First, we give a recurrence for the number of length-n words with largest BP-factorization of width t. Second, we show that the expected width of the largest BP-factorization of a word tends to a constant. Third, we give some results on another extremal variation of BP-factorization, the smallest BP-factorization. A border of a word w is a non-empty word that is both a proper prefix and suffix of w. Finally, we conclude by showing a connection between words with a unique border and words whose smallest and largest BP-factorizations coincide.
READ FULL TEXT