FPRD-T91 · visible projection

Context-free languages are exactly projections of visibly pushdown languages

Put $S=\{\mathsf c,\mathsf r,\mathsf l\}$, let $\widehat\Sigma=\Sigma\times S$, and let $\pi(a,s)=a$. Then

For the forward direction, normalize a pushdown automaton so that each letter-reading transition pushes, pops, or leaves the stack height unchanged. Tag the letter by that action. The tag now makes the stack discipline visible, and forgetting it recovers the original word. The tagged language may be determinized before the projection. The converse follows because visibly pushdown languages are context-free and context-free languages are closed under homomorphism.

The projection is letter-to-letter and length preserving: no terminal is erased. The empty word has its unique empty tagged lift. Determinism belongs to the tagged automaton; it does not make the projected language deterministic context-free.

FPRD-T164 · FPRD-C02 resolved

Not every forgotten-action visible language is a PEG language

FPRD-T91 identifies the whole forgotten-action class, not merely one positive tier:

Kim and Park now supply a language$L=C^R\in\mathsf{LIN}\setminus\mathsf{PEG}$. Since $\mathsf{LIN}\subseteq\mathsf{CFL}$, FPRD-T91 gives a deterministic visibly pushdown language whose action-forgetting projection is exactly L. Therefore

This is a short composition of two source results. FPRD Lab does not claim an independent proof of the Kim-Park separation.

FPRD-T165 · directional visible lifts

The two reversal directions fail for different reasons

Apply FPRD-T91 separately to both linear languages in the Kim-Park pair. There are deterministic visible lifts with

The first lift is the hard calibration for stationary frontier transport: no scaffold recognizes its projection. The second is the direct counterexample to FPRD-C02: its projection is not PEG, even though a scaffold does recognize it.

There is no contradiction. The exact orientation is

A stationary frontier presentation for X gives a scaffold for X and therefore a PEG for$X^R$. PEG membership of X is controlled by stationary transport on the reversed language.

• Complete composition and orientation proof
• Implication checker
• Recorded checker output
• Kim and Park: PEG separation

The checker verifies only the logical composition and reversal orientation. It does not reverify the imported separation, its Lean artifact, or the underlying cell-probe lower bound.

FPRD-D33 · frontier model

The hidden actions generate a finite frontier after every prefix

Use a finite real-time top-rewriting machine with transitions$(q,a,X,q',\gamma)$. If the stack is $Xv$, the transition consumes$a$ and replaces the stack by$\gamma v$. There are no epsilon transitions, endmarker transitions, or steps after the input ends.

For a prefix $u$, define

Each set is finite for fixed $u$: every run has exactly $|u|$steps and each step chooses from one finite transition table. This finiteness does not provide a uniform online representation bound.

FPRD-T92 · checked recurrence

One left derivative gives the exact next frontier

Write $X^{-1}B=\{v:Xv\in B\}$. Splitting a run before its last transition gives the exact identity

Conversely, any stack in a term on the right extends a run on$u$ by the displayed transition. Final-state acceptance is exactly

The standalone Lean development checks the executable transition system, this recurrence, the readout, the empty-word case, and concrete push, pop, local, union, and failed-top examples.

FPRD-T93 · finite-core criterion

Uniformly bounded finite-horizon fits sew into one recognizer

Fix nested finite families$\mathcal K_0\subseteq\mathcal K_1\subseteq\cdots$of canonically normalized scaffolding automata, with the index bounding every part of the finite source. Let$e_L(N)$ be the least$k$ for which a machine in$\mathcal K_k$ agrees with$L^R$ on words of length at most$N$. Then

One parsing expression grammar yields one scaffold for the reversed language, so its stratum bounds every horizon. Conversely, if all horizons fit one fixed finite stratum, some machine in that stratum recurs at unbounded horizons. For any word, choose a recurring horizon at least its length; that one machine agrees with$L^R$ everywhere.

Finiteness after canonical normalization is essential. The theorem is not a compactness argument for an arbitrary infinite resource class.

FPRD-T94 · stationary-cover transfer

A stationary exact cover compiles to the same language

A stationary derivative cover fixes one derivative basis, a finite set of slots, one synchronous multistack update, a validity invariant, and one readout. It must satisfy four obligations: exact initialization, preservation of the invariant, exact one-letter frontier update, and exact final-state readout. These data form one horizon-independent representation.

Induction on the input then proves that the relation represented after every word is exactly the pushdown frontier. The checked FPRD compiler preserves the executor's decisions, so the resulting scaffold recognizes exactly the same language, including at epsilon. One-slot visible-stack and two-slot parallel examples both instantiate the interface.

If the source and cover carriers are finite, the compiled object is a finite scaffolding automaton. The external scaffold-to-PEG theorem then yields a PEG for the reversed source language. The orientation matters: a cover for $X$ gives$X^R\in\mathsf{PEL}$ through this composition.

FPRD-T112 · exact normalization

Derivative access can be made local by spending cover width

A principal term consists of a concrete stack stem$v$ and a basis language$B_j$. A finite cover denotes

If the stem begins with the queried symbol, differentiation removes that symbol. If it begins with another symbol, the derivative is empty. If the stem is empty, a supplied finite derivative table for$B_j$ replaces the term. Lean checks this case split and its extension across finite unions:

There is also an exact calibration at the other extreme. Using only the epsilon basis, any finite listed frontier$F=[z_1,\ldots,z_m]$ has a cover with one term per listed stack:

This changes the diagnosis, not the open problem. Flattening makes derivative access local by spending width. It does not bound slot count, basis or control complexity, fresh allocation, or the cost of a stationary canonicalizer. Derivative depth alone is therefore not a representation-independent obstruction.

The universal question is closed; the structural boundary remains

The exact frontier update is settled, and any stationary cover that satisfies the local interface compiles correctly. Kim and Park's separation now proves that no such construction can work for every projected visible frontier. A visible lift of their language C is an explicit existential obstruction: its projection is outside SCA.

What remains open is intrinsic characterization. Which projected frontiers admit bounded stationary transport, and which context-free languages lie in PEG? The existing allocator tiers give sufficient conditions. The C lift supplies a hard calibration against which a representation-independent lower-bound invariant can now be tested. FPRD-T168 further shows that its tagged language needs only one persistent stack, but its accepting lifts admit no fixed finite causal-selector cover after the action tags are hidden.