The forgotten-action question is resolved negatively

Result

Let FA-DVPL be the class of languages obtained by taking a deterministic visibly pushdown language over letters tagged call, return, or local and then forgetting the action tag at every position.

Earlier FPRD records use PEL for the class of parsing-expression languages. This note uses PEG, following Kim and Park; the class intended here is the same.

FPRD-T91, following Alur and Madhusudan, gives the exact class identity

$$\mathsf{FA\text{-}DVPL}=\mathsf{CFL}.$$

Kim and Park construct a language C such that

$$C\in\mathsf{LIN}\cap\mathsf{PEG}\setminus\mathsf{SCA}, \qquad L=C^R\in\mathsf{LIN}\cap\mathsf{SCA}\setminus\mathsf{PEG}.$$

Since LIN is contained in CFL, both C and L have deterministic visibly pushdown lifts whose action-forgetting projections are exactly C and L.

FPRD-T164: Negative resolution of FPRD-C02

Theorem. There is a deterministic visibly pushdown language A such that its forgotten-action projection is not a parsing-expression language.

Equivalently,

$$\mathsf{FA\text{-}DVPL}\nsubseteq\mathsf{PEG}.$$

Proof. Put L=C^R for the Kim-Park witness. Their Theorem 4.19 gives L in LIN minus PEG. Hence L is context-free. By FPRD-T91 there is a deterministic visibly pushdown language A whose action-forgetting projection is L. Therefore that projection is not in PEG. QED.

This closes FPRD-C02 negatively. The earlier wording of the program treated the universal question as open because it had not yet incorporated the August 30, 2026 Kim-Park separation.

FPRD-T165: The two-sided visible-lift separation

Theorem. There are deterministic visibly pushdown languages A_C and A_L whose forgotten-action projections satisfy

$$\pi(A_C)=C\in\mathsf{LIN}\cap\mathsf{PEG}\setminus\mathsf{SCA},$$

and

$$\pi(A_L)=L=C^R\in\mathsf{LIN}\cap\mathsf{SCA}\setminus\mathsf{PEG}.$$

Proof. Kim and Park prove the two class memberships and linear context-freeness. Apply FPRD-T91 separately to C and L. QED.

The two lifts expose different obstructions.

• A_C is the stationary-transport-hard side. Its projection C has empty scaffold transport spectrum.
• A_L is the parsing-hard side. Its projection L is not PEG, although L itself is scaffold-recognizable.

These facts are compatible because PEG and SCA are related by reversal, not equality.

Reversal-side transport criterion

For every language X, the Loff-Moreira-Reis characterization and FPRD-T161 give

$$X\in\mathsf{PEG} \quad\Longleftrightarrow\quad X^R\in\mathsf{SCA} \quad\Longleftrightarrow\quad \delta_{\mathrm{str}}(X^R)<\infty.$$

For L=C^R this becomes

$$\delta_{\mathrm{str}}(L)<\infty, \qquad \delta_{\mathrm{str}}(L^R)=\delta_{\mathrm{str}}(C)=\infty, \qquad L\notin\mathsf{PEG}.$$

Thus the stationary transport obstruction controlling PEG membership of X lives on X^R. A scaffold for X proves that X^R has a PEG; it does not prove that X has a PEG.

What survives from the frontier program

The positive allocator and cover theorems remain correct. Their exact orientation is:

$$\text{stationary frontier presentation for }X \Longrightarrow X\in\mathsf{SCA} \Longrightarrow X^R\in\mathsf{PEG}.$$

They therefore identify genuine positive subclasses and reusable compilers. They cannot hold for every forgotten-action frontier, because the visible lift A_C projects to C outside SCA.

The new open problem is no longer whether every forgotten-action projection is PEG. It is to characterize the directional subclasses

$$\mathsf{CFL}\cap\mathsf{SCA} \quad\text{and}\quad \mathsf{CFL}\cap\mathsf{PEG},$$

and to find intrinsic frontier properties that distinguish the transport-hard lift A_C from positive allocator tiers.

Dependency boundary

The class identity FA-DVPL=CFL is the previously source-verified FPRD-T91. The separation is imported from Kim and Park, Theorem 4.19. This note proves only the short composition and its reversal orientation. It does not independently recheck the Kim-Park Lean artifact, their SCA-to-cell-probe theorem, or Ko’s lower bound.

Sources

• Rajeev Alur and P. Madhusudan, Visibly Pushdown Languages, STOC 2004. FPRD-T91 records the action-tag construction and determinization boundary.
• Jungyeom Kim and Jihyeok Park, Separating Parsing Expression Grammars using Cell-Probe Lower Bounds, arXiv:2608.29592v1: https://arxiv.org/abs/2608.29592
• Alexander Loff, Nelma Moreira, and Rogério Reis, The Computational Power of Parsing Expression Grammars, arXiv:1902.08272: https://arxiv.org/abs/1902.08272