๐Ÿ“–
Small Space Encoding and Recognition of k-Palindromic Prefixes
Gabriel Bathie, Jonas Ellert, Tatiana Starikovskaya

Small Space Encoding and Recognition of k-Palindromic Prefixes

Science & Mathematics Published 2025 Verification Pending

Overview & Synopsis

Palindromes are non-empty strings that read the same forward and backward. The problem of recognizing strings that can be represented as the concatenation of even-length palindromes, the concatenation of palindromes of length at least two, and the concatenation of exactly $k$ palindromes was introduced in the seminal paper of Knuth, Morris, and Pratt [SIAM J. Comput., 1977]. In this work, we study the problem of recognizing so-called \emph{$k$-palindromic} strings, which can be represented as the concatenation of exactly $k$ palindromes. It was shown that the problem is solvable in linear space and time [Rubinchik and Shur, MFCS 2020]. We aim to develop a sublinear-space solution, and show the following results: \begin{enumerate} \item First, we show a structural characterization of the set of all $k$-palindromic prefixes of a string by representing it as a union of a small number of highly structured string sets, called \textit{affine prefix sets}. Representing the lengths of the $k$-palindromic prefixes in this way requires $\Oh(6^{k^2} \cdot \log^k n)$ space. By constructing a lower bound, we show that the space complexity is optimal up to polylogarithmic factors for reasonably small values of $k$. \item Secondly, we derive a read-only algorithm that, given a string $T$ of length $n$ and an integer~$k$, computes a compact representation of $i$-palindromic prefixes of $T$, for all $1 \le i \le k$. The algorithm uses $\Oh(n \cdot 6^{k^2} \cdot \log^k n)$ time and $\Oh(6^{k^2} \cdot \log^k n)$ space. \item Finally, we also give a read-only algorithm for computing the palindromic length of $T$, which is the smallest $\ell$ such that $T$ is $\ell$-palindromic. Here, we achieve $\Oh(n \cdot 6^{\ell^2} \cdot \log^{\ceil{\ell/2}} n)$ time and $\Oh(6^{\ell^2} \cdot \log^{\ceil{\ell/2}} n)$ space. For some values of $\ell$, this is the first algorithm for palindromic length that uses $o(n)$ additional working space on top of the input. \end{enumerate}

Indexed from repository: HAL Open Science (hal.science)
Loading document from verified source...
Keyboard Shortcuts: ← / → for pages • + / - for zoom • 0 to fit width Powered by Mozilla PDF.js v3.11

Document Information

Document Title Small Space Encoding and Recognition of k-Palindromic Prefixes
Author / Organization Gabriel Bathie, Jonas Ellert, Tatiana Starikovskaya
Subject & Discipline Multidisciplinary Academic Open Research
Categories Science & Mathematics
Publication Year 2025
License / Rights Open Access / Creative Commons
Resource Verification Listed PDF (Verification Pending)
Original Host Website HAL Open Science (hal.science)
File Format application/pdf (Portable Document Format)
Language EN
Catalog ID DOC-184347
Original Source Link Visit Source Page on hal.science »