Forgotten-action lifts exhibit both sides of the PEG-SCA separation

Exact statement

For the Kim-Park witness pair $L=C^R$ , there are deterministic visibly pushdown languages $A_C,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\in\mathsf{LIN}\cap\mathsf{SCA}\setminus\mathsf{PEG}$ . Thus one projected frontier is stationary-transport hard while the other is PEG hard, and the two obstructions are exchanged by reversal.

StatusSource-attributed composition of FPRD-T91 with Kim-Park Theorem 4.19

External reviewThe separation is imported from Kim and Park, arXiv:2608.29592v1. FPRD Lab has checked the class composition and reversal orientation, not independently rerun their Lean artifact.

Context

Every context-free language has a deterministic visible lift after action tags are introduced. Applying this separately to both sides of the Kim-Park reversal pair identifies two different frontier obstructions.

Hypotheses and scope

The FPRD-T91 visible lift preserves the underlying word by forgetting exactly one action tag per position.
Kim-Park Theorem 4.19 supplies the exact PEG and SCA memberships of C and C^R.

Proof or evidence

Both witness languages are linear context-free, so FPRD-T91 supplies deterministic visible lifts. C lies outside SCA and therefore has infinite structural degree; C^R lies inside SCA but outside PEG.

Two-sided visible-lift theorem →

Verification notes

The checker verifies both lift inferences, both structural-degree conclusions, and both directions of the PEG-reverse-SCA orientation.

Limitations

The theorem does not give a small explicit visibly pushdown automaton for either lift.
It imports the Kim-Park separation and does not independently prove their cell-probe lower bound.
Transport-hard and PEG-hard refer to different sides of the reversal pair.

Open work

Use a visible lift of C, rather than of C^R, as the hard calibration for intrinsic stationary-frontier lower bounds.