FPRD LabShare an approach

PEG computational models

Status: source-audited literature map; no new FPRD claim.

Scope: Rubtsov–Chudinov's pointer pushdown model, the Loff–Moreira–Reis scaffolding model, Kim–Park's cell-probe lower-bound bridge, and their relationship to FPRD's scaffold research.

This map adds external work to the lab's shared frame of reference. It does not revise the three FPRD papers, and the external papers cited here do not constitute review of them.

The common language observation

All four viewpoints below ultimately ask whether a complete input belongs to a language, but they retain different internal information on the way to that one-bit observation.

Viewpoint Persistent information One step can inspect or revisit Exact language relationship
Parsing expression grammar (PEG) recursive parsing state and ordered failure/success behavior the expression can invoke subexpressions and lookahead from the current suffix defines the class PEG, also called PEL in Rubtsov–Chudinov
Deterministic pointer pushdown automaton (DPPDA) one LIFO stack whose symbols remember their push positions a pop may return the input head to the stored push position Rubtsov–Chudinov prove DPPDA = PEG
Scaffolding automaton (SCA) one append-only graph node per input symbol, with finitely many backward/self pointers a fixed-radius neighborhood of the current top Loff–Moreira–Reis prove H∈PEGH\in\mathsf{PEG} iff HRH^R is SCA-decidable
FPRD scaffold dynamics a chosen SCA-style presentation together with physical history and selected behavioral quotients whatever the fixed finite presentation and observation interface expose no new language class is asserted merely by retaining this structure

The two automaton characterizations should therefore not be collapsed into one picture. A DPPDA organizes history as nested returns on a stack. An SCA organizes history chronologically as an immutable graph. They meet at the language level—after accounting for the SCA reversal—but a direct translation that preserves their presentation structure and quantitative resources is a separate theorem, not a consequence of language equivalence.

What Rubtsov and Chudinov add

Rubtsov and Chudinov give PEGs a compact machine interpretation. Every stack entry carries a return address into the input, and popping can restore that address. Their full construction translates PEGs to DPPDAs and DPPDAs back to PEGs. They also give an O(n)O(n)-time RAM simulation of the two-way extension.

Their closure results identify a substantial positive composition tier. If XX is deterministic context-free and YY is a PEG language, then XYXY is a PEG language. More generally, Boolean combinations of the regular closure of deterministic context-free languages lie in PEG, and PEG is closed under left concatenation by that regular closure.

This gives FPRD a useful comparator for any construction described as “remember a position and resume from it.” The comparison is strongest when the remembered dependencies are properly nested. It is weaker when an FPRD presentation relies on simultaneous records, non-LIFO sharing, or distinctions among physical history, prefix trace, and final observation.

What Kim and Park change

Kim and Park construct one language CC with

C∈LIN∩PEGbutCR∈LIN∖PEG. C\in\mathsf{LIN}\cap\mathsf{PEG} \quad\text{but}\quad C^R\in\mathsf{LIN}\setminus\mathsf{PEG}.

This answers two old questions: not every context-free language has a PEG, and PEG is not closed under reversal. The same witness also proves

PEG⋅REG⊈PEG. \mathsf{PEG}\cdot\mathsf{REG} \not\subseteq\mathsf{PEG}.

That negative result and Rubtsov–Chudinov's positive theorem fit together cleanly:

Orientation Current result
regular or regular-closure language on the left of a PEG language positive; Rubtsov–Chudinov prove the stronger ΓREG(DCFL)⋅PEG=PEG\Gamma_{\mathrm{REG}}(\mathsf{DCFL})\cdot\mathsf{PEG}=\mathsf{PEG}
regular language on the right of a PEG language negative in general; Kim–Park prove PEG⋅REG⊈PEG\mathsf{PEG}\cdot\mathsf{REG}\not\subseteq\mathsf{PEG}

The new lower-bound method is itself relevant to FPRD. Kim and Park serialize preprocessing, updates, and a final query as one language. A fixed-radius SCA would yield an exact deterministic cell-probe data structure with probe costs controlled by the serialized update and query lengths. A suitable cell-probe lower bound can therefore exclude an SCA, and reversal then excludes a PEG. This is the first source-audited negative method in the lab map that uses the SCA access restriction directly.

The palindrome question stays separate

Kim and Park explicitly say that their witness is not the palindrome language. Their separation therefore does not settle the palindrome question. Nor does nonclosure under reversal say that a particular self-reversing language is outside PEG.

FPRD currently has three papers relevant to this neighborhood. They are all awaiting specialist review:

Paper Connection to this map
Real-time multitape languages transfer to parsing expression grammars compiles strict real-time multitape computation into scaffolding automata and then uses the published SCA–PEG theorem
Persistent receipts and simultaneous records: a direct scaffold for even palindromes proposes a direct SCA construction for binary even palindromes
Persistent scaffold computation: causal presentations, sewing, and feedback studies scaffold histories and their presentation-level equivalences rather than introducing another PEG language class

The shared review status matters: none of the three has received specialist review, and neither Rubtsov–Chudinov nor Kim–Park should be described as having validated any of them. The model map is context for readers, not an endorsement claim.

What the lab should retain

  1. Nested return addresses are a canonical PEG coordinate. DPPDAs give a clean stack-machine account of ordered backtracking.
  2. Chronological persistence exposes a different resource. SCAs retain the full construction history but restrict each online step to bounded local access.
  3. Orientation is part of a theorem. Left and right concatenation now have provably different closure behavior.
  4. Extensional equivalence does not identify dynamics. Equivalent language models can expose different histories, actions, and resource measures.
  5. A direct DPPDA–SCA compiler is a worthwhile open comparison. Any such work should state whether it preserves only language, or also time, stack height, scaffold degree, view radius, and presentation structure.

Primary sources and detailed notes