Separating Parsing Expression Grammars using Cell-Probe Lower Bounds

We resolve three open problems concerning parsing expression grammars (PEGs). We construct a single language $C$ satisfying $C\in \mathsf{L}\mathsf{I}\mathsf{N}\cap \mathsf{P}\mathsf{E}\mathsf{G}$ and $C^R\in \mathsf{L}\mathsf{I}\mathsf{N}\setminus \mathsf{P}\mathsf{E}\mathsf{G}$. This proves that some linear context-free language is not a PEG language and that PEG languages are not closed under reversal, confirming a conjecture of Loff, Moreira, and Reis. Factoring the same witness resolves the concatenation-closure problem of Rubtsov and Chudinov negatively, in the strong form $\mathsf{P}\mathsf{E}\mathsf{G}\cdot \mathsf{R}\mathsf{E}\mathsf{G}\subseteq ̸\mathsf{P}\mathsf{E}\mathsf{G}$ despite $\mathsf{R}\mathsf{E}\mathsf{G}\cdot \mathsf{P}\mathsf{E}\mathsf{G}\subseteq \mathsf{P}\mathsf{E}\mathsf{G}$. It also refutes closure under Kleene star, homomorphisms, and substitutions. Our main technique converts scaffolding automata (SCAs), which characterize reversals of PEG languages, into dynamic data structures in the cell-probe model. For any suitably local serialization of a problem with preprocessing, updates, and a final Boolean query, an SCA recognizer yields an exact deterministic cell-probe data structure whose operation costs are proportional to the corresponding encoding lengths. Cell-probe lower bounds can therefore prove SCA non-membership and, by reversal, PEG non-membership. We apply this transfer to Multiphase Inner Product using one-symbol update blocks and a query suffix of length $O(\log n)$, while keeping both the language and its reversal linear context-free. Ko’s cell-probe lower bound then yields the witness above. The arguments are additionally formalized in Lean 4.