FPRD LabShare an approach

Cell-probe obstructions to stationary transport

Contents

Scope

This note translates the SCA-to-cell-probe transfer of Jungyeom Kim and Jihyeok Park into the stationary-transport language of FPRD-T157 and the canonical structural degree of FPRD-T161. It does not reprove their transfer theorem, Young Kun Ko’s cell-probe lower bound, or the Lean artifact accompanying Kim and Park’s paper.

The new content is the exact interface with the FPRD invariant and the resulting directional statement for structural degree. Both results are source-attributed corollaries.

Definitions

For a language K, let Tr(K) be its stationary transport spectrum: the resource tuples of finite scaffolding automata recognizing K. By FPRD-T161, define

δstr(K)=min⁡{D:(D,2,1,2)∈Tr⁡(K)}, \delta_{\mathrm{str}}(K) = \min\{D:(D,2,1,2)\in\operatorname{Tr}(K)\},

with value infinity when the set is empty. Thus

δstr(K)<∞⟺Tr⁡(K)≠∅⟺K∈SCA. \delta_{\mathrm{str}}(K)<\infty \quad\Longleftrightarrow\quad \operatorname{Tr}(K)\ne\varnothing \quad\Longleftrightarrow\quad K\in\mathsf{SCA}.

Kim and Park define an (a,b)-SCA encoding of a three-stage Boolean data-structure problem. A complete word consists of a preprocessing prefix, sequential update blocks of length at most a(n), and a final query suffix of length at most b(n). Its total length is polynomial in n, and membership returns the exact Boolean answer.

FPRD-T162: Cell-probe obstruction to finite stationary transport

Theorem. Let K be an (a,b)-SCA encoding of a three-stage Boolean problem in the sense of Kim and Park. Suppose there is no exact deterministic cell-probe data structure for that problem with all four of the following properties:

  1. word size Theta(log n);
  2. update time O(a(n));
  3. query time O(b(n));
  4. polynomially many memory cells.

Then

Tr⁡(K)=∅andδstr(K)=∞. \operatorname{Tr}(K)=\varnothing \qquad\text{and}\qquad \delta_{\mathrm{str}}(K)=\infty.

Proof. Assume that delta_str(K) is finite. FPRD-T161 then gives a finite scaffolding automaton recognizing K. Kim and Park’s Theorem 3.5 converts that fixed automaton and the (a,b)-encoding into an exact deterministic cell-probe data structure with word size Theta(log n), update time O(a(n)), query time O(b(n)), and polynomial space. This contradicts the hypothesis. Therefore delta_str(K) is infinite. Its equivalence with an empty transport spectrum follows from the definition and FPRD-T161. QED.

The constants in the cell-probe bounds may depend on the candidate automaton. This is harmless: a lower bound excluding every data structure with the stated asymptotic bounds excludes every finite structural degree D at once.

FPRD-T163: Reversal can change finite structural degree to infinity

Kim and Park construct a record-first language C and prove

C∈LIN∩PEG∖SCA,CR∈LIN∩SCA∖PEG. C\in\mathsf{LIN}\cap\mathsf{PEG}\setminus\mathsf{SCA}, \qquad C^R\in\mathsf{LIN}\cap\mathsf{SCA}\setminus\mathsf{PEG}.

Corollary. There is a linear context-free language C such that

δstr(C)=∞,δstr(CR)<∞. \delta_{\mathrm{str}}(C)=\infty, \qquad \delta_{\mathrm{str}}(C^R)<\infty.

Proof. Apply the equivalence between finite structural degree and SCA recognition to the two membership statements above. QED.

This is an exact directional asymmetry inside the linear context-free languages. It concerns the ability to maintain a bounded-locality persistent presentation while reading in one direction. It is stronger than saying that one convenient encoding fails.

The hard transport pattern

For Kim and Park’s witness, the preprocessing phase stores N(n)=n^2 binary vectors. The n updates reveal one query vector one coordinate at a time, using one input symbol per update. Only after all updates does the final suffix reveal which stored vector must be paired with the update vector. The query suffix has length

β(n)=⌈log⁡2(n2+1)⌉+1=O(log⁡n). \beta(n)=\left\lceil\log_2(n^2+1)\right\rceil+1=O(\log n).

If C had any fixed scaffold presentation, each update would cost O(1) cell probes and the final query O(log n) probes. Ko’s lower bound for Multiphase Inner Product excludes that combination. This is the missing encoding-robust feature that raw response-row counting did not provide: the query is disclosed after the persistent state has been built, and the bound charges the work needed to reach the requested information.

Relation to the replayable-memory program

The result sharpens the four-resource strategy.

  • Operational support is not the obstruction. One completed query may inspect a small part of memory.
  • Semantic support and quotient size are not enough. FPRD-T154 showed that raw finite-horizon row counts cannot separate all scaffolds.
  • Fixed future tests are not the obstruction. FPRD-T158 compiles every fixed finite suffix family.
  • The hard resource is delayed, growing access demand. The updates finish before the logarithmic query identifies which preprocessed vector matters.

This also explains why the persistent selector remains easy. A persistent stack can answer an index encoded in O(log n) symbols with O(log n) local work. Multiphase Inner Product is different: Ko’s theorem proves that after constant-cost updates, the final query requires superlogarithmic probes.

Consequence for FPRD-C02

Together with FPRD-T91, the Kim-Park separation does decide FPRD-C02. Forgotten-action projections of deterministic visibly pushdown languages are exactly the context-free languages, while Kim and Park prove that some linear context-free language is not PEG. Therefore the universal forgotten-action PEG statement is false.

The reversal orientation matters. Their record-first language C is outside SCA and is the hard calibration for stationary frontier transport. Its reversal L=C^R is inside SCA but outside PEG and is the direct counterexample to FPRD-C02. Both are context-free and therefore both have deterministic visible lifts.

This correction is developed as FPRD-T164 and FPRD-T165. The remaining problem is to characterize positive projected-frontier subclasses and find an intrinsic reason why a visible lift of C cannot have bounded stationary transport.

What remains open

Kim and Park explicitly note that their method does not isolate an intrinsic combinatorial obstruction for scaffolds. A direct invariant of append-only persistent graphs and fixed-radius access remains open. FPRD’s stationary-transport program can now pursue that intrinsic theory with one externally established hard family as a calibration target.

Their result confirms the Loff-Moreira-Reis conjecture that PEG languages are not closed under reversal. It does not settle the separate question of whether the palindrome language has a PEG.

Sources

  • Jungyeom Kim and Jihyeok Park, Separating Parsing Expression Grammars using Cell-Probe Lower Bounds, arXiv:2608.29592v1, especially Definition 3.2, Theorem 3.5, Proposition 4.17, and Theorem 4.19: https://arxiv.org/abs/2608.29592
  • Young Kun Ko, An Omega((log n/log log n)^2) Cell-Probe Lower Bound for Dynamic Boolean Data Structures, arXiv:2603.25914v1: https://arxiv.org/abs/2603.25914

Verification boundary

The accompanying checker verifies the elementary parameter arithmetic and the logical orientation of the FPRD translation. It does not verify either source paper, their formalization, or the cell-probe lower bound. Those are imported dependencies.