Small Space Encoding and Recognition of k-Palindromic Prefixes
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}
hal.science)
← / → 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 » |