Smallest and Largest Block Palindrome Factorizations

DOI10.1007/978-3-031-33180-0_14zbMATH Open1529.68237arXiv2302.13147OpenAlexW4381304387MaRDI QIDQ6134873FDOQ6134873

Daniel Gabric, Jeffrey Shallit

Publication date: 25 July 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Abstract: A emph{palindrome} is a word that reads the same forwards and backwards. A emph{block palindrome factorization} (or emph{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 emph{width} of the BP-factorization. The emph{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 emph{smallest BP-factorization}. A emph{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.

Full work available at URL: https://arxiv.org/abs/2302.13147

zbMATH Keywords

factorizationrecurrenceunbordered wordblock palindromeunique border

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• A note on bifix-free sequences (Corresp.)
• Searching for gapped palindromes
• On palindromic factorization of words
• On the palindromic decomposition of binary words
• Block reversal on finite words
• Rich words in the block reversal of a word
• Enumeration of bordered words, le langage de la vache-qui-rit
• Maximal unbordered factors of random strings
• Counting bordered and primitive words with a fixed weight
• Block palindromes: a new generalization of palindromes

Cited In (2)

• On highly palindromic words: the \(n\)-ary case
• A subquadratic algorithm for minimum palindromic factorization

This page was built for publication: Smallest and Largest Block Palindrome Factorizations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6134873)