2023/02/25 by Daniel Gabrić, Jeffrey Shallit, Gabric, Daniel +1
Biochemistry, Genetics and Molecular Biology · Computer Science · #Coding theory and cryptography #Combinatorics (math.CO) #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2302.13147
openalex publication_date 2023/02/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.