Prefix-Free Parsing (PFP) enables efficient indexing of repetitive text collections through dictionary-based storage of distinct factors and the corresponding factor positions in the text. The parsing method of PFP differs from LZ78 compression as it separates factors at occurrences of predefined trigger strings, ensuring that the parse is prefix-free. This prefix-free property of PFP makes it suitable for compressed indexing applications such as the construction of the Burrows-Wheeler Transform. Recent work has also introduced a recursive PFP technique, in which the parse of the initial PFP is further compressed with an additional round of prefix-free parsing. In this paper, we provide a theoretical analysis of the minimal size of any prefix-free parse. We show that for a PFP of a string of length$n$, the sum of the lengths of the parse string and the number of nodes in the trie of dictionary strings must be at least$2 \sqrt{n}$. We generalize this result by demonstrating that if prefix-free parsing is applied recursively$k$times, the combined size of the dictionary tries at each level and the final parse must be at least$(k+1) \cdot n^{1 /(k+1)}$. We also provide a family of strings and corresponding trigger strings that achieve this lower bound, demonstrating its tightness and a polynomially large separation between PFP and several other popular compressibility measures. Finally, we illustrate that optimal PFP - that is, with optimal trigger string selection - is robust against one-bit catastrophes for some strings where LZ78 is not. This demonstrates that the optimal PFP size cannot be guaranteed to be within a multiplicative ratio polynomially smaller than$n^{1 / 8}$relative to the LZ78 size.

We revisit the Contextual Pattern Matching Problem, defined as follows: preprocess a text T[1, n], so that given a query consisting of a string P and a length P, the occurrences of all distinct strings XPY where |X|=|Y|=P can be reported. This problem was introduced by Navarro, who presented an O($\overline{r}\log(n/\overline{r}))$ space data structure, where $\overline{r}$ is the maximum of the number of runs in the BWT of the text $\mathrm{T}[1,n]$ and its reverse. His solution reports all c contextual occurrences in $O(|P|+c\log n)$ time. However, the only known bounds on $\overline{r}$ are $\overline{r}=O(r\log^{2}n)$ where r is the number of runs in the BWT of T, making it desirable to avoid using structures with space dependent on $\overline{r}$. We demonstrate that this is possible without a significant sacrifice in query time by providing an $O(r\log(n/r))$ space solution that answers queries in $O(|P|+c\log P\cdot\log(n/r))$ time.