Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Notes
- 1.
Largest BP-factorizations also appear in https://www.reddit.com/r/math/comments/ga2iyo/i_just_defined_the_palindromity_function_on/.
References
Nielsen, P.T.: A note on bifix-free sequences. IEEE Trans. Inform. Theory, IT-19, 704–706 (1973)
The 2015 British Informatics Olympiad (Round 1 Question 1). https://olympiad.org.uk/2015/index.html
Goto, K., Tomohiro, I., Bannai, H., Inenaga, S.: Block palindromes: a new generalization of palindromes. In: Gagie, T., Moffat, A., Navarro, G., Cuadros-Vargas, E. (eds.) SPIRE 2018. LNCS, vol. 11147, pp. 183–190. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-00479-8_15
Mahalingam, K., Maity, A., Pandoh, P., Raghavan, R.: Block reversal on finite words. Theoret. Comput. Sci. 894, 135–151 (2021)
Mahalingam, K., Maity, A., Pandoh, P.: Rich words in the block reversal of a word. Discrete Appl. Math. 334, 127–138 (2023). https://doi.org/10.1016/j.dam.2023.03.013
Kolpakov, R., Kucherov, G.: Searching for gapped palindromes. Theoret. Comput. Sci. 410(51), 5365–5373 (2009)
Régnier, M.: Enumeration of bordered words, le langage de la vache-qui-rit. RAIRO-Theor. Inf. Appl. 26(4), 303–317 (1992)
Frid, A.E., Puzynina, S., Zamboni, L.Q.: On palindromic factorization of words. Adv. in Appl. Math. 50(5), 737–748 (2013)
Ravsky, O.: On the palindromic decomposition of binary words. J. Autom. Lang. Comb. 8(1), 75–83 (2003)
Sloane, N.J.A., et al.: OEIS Foundation Inc. The On-Line Encyclopedia of Integer Sequences (2022). https://oeis.org
Cording, P.H., Gagie, T., Knudsen, M.B.T., Kociumaka, T.: Maximal unbordered factors of random strings. Theoret. Comput. Sci. 852, 78–83 (2021)
Harju, T., Nowotka, D.: Counting bordered and primitive words with a fixed weight. Theoret. Comput. Sci. 340(2), 273–279 (2005)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Gabric, D., Shallit, J. (2023). Smallest and Largest Block Palindrome Factorizations. In: Frid, A., Mercaş, R. (eds) Combinatorics on Words. WORDS 2023. Lecture Notes in Computer Science, vol 13899. Springer, Cham. https://doi.org/10.1007/978-3-031-33180-0_14
Download citation
DOI: https://doi.org/10.1007/978-3-031-33180-0_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-33179-4
Online ISBN: 978-3-031-33180-0
eBook Packages: Computer ScienceComputer Science (R0)