Theorems

Loff–Moreira–Reis [7, Theorem 16, p. 21]

(Loff–Moreira–Reis [7, Theorem 16, p. 21] ). A language $L\subseteq\Sigma^*$ is in $\mathsf{PEG}$ if and only if its reversal $L^R$ is decided by some scaffolding automaton. In particular, if a finite scaffolding automaton decides $L$ , then $L^R$ is recognized by a total complete-match PEG.

Occurrence-context factorization

After reading $a$ , the new longest even suffix $P'$ and reversed context $\ell'$ are exactly $$(P',\ell')= \begin{cases} (aPa,\ell_0), &\ell=a\ell_0,\\[1mm] (aD_a(P)a,\omega_a(P)\ell), &\ell\notin a\Sigma^*,\ D_a(P)\text{ defined},\\[1mm] (\epsilon,aP\ell), &\ell\notin a\Sigma^*,\ D_a(P)\text{ undefined}. \end{cases}$$…

chunk recursion

Let $P$ be a nonempty even palindrome with suffix link $L=\lambda(P)$ , bridge $b$ , and bridge block $B_P$ . Then $$D_b(P)=L,\qquad \omega_b(P)=B_P,$$ and for every letter $a\ne b$ , $$D_a(P)=D_a(L),\qquad \omega_a(P)=\omega_a(L)\,b\,B_P,$$ with the same definedness on both sides (for $L=\epsilon$ the r…

Typed mirror receipt

Suppose an update selects a longest suffix occurrence $Q$ of the old input that is immediately preceded by $a$ , and creates $Y=aQa$ . Then $$\lambda(Y)= \begin{cases} aD_a(Q)a,&D_a(Q)\text{ defined},\\ \epsilon,&D_a(Q)\text{ undefined}. \end{cases}$$ The palindrome $\lambda(Y)$ has a complete occurrence in…

Endpoint-only escape

For $m\ge2$ , let $S_m=0^{2m}1100$ . Its longest even-palindromic suffix is $001100$ and the suffix link is $00$ . The mirror occurrence of $00$ ends at the historical prefix $0^{2m}$ , whose longest suffix-link chain is $$0^{2m},0^{2m-2},\ldots,00,\epsilon.$$ Recovering $00$ from that untyped endpoint…

Future transition after type birth

For $r\geq1$ , put $A_r=0^{2r}$ , $$P_r=A_r11A_r, \qquad T_r=1A_r1.$$ Then $D_1(P_r)=A_r$ , so the transition selected by $1$ has target $T_r=1D_1(P_r)1$ . The type $P_r$ is born by the end of the prefix $P_r$ , but $T_r$ is not a factor of that prefix. It becomes available only in a later history su…

Anchor dependence

For the fixed one-letter block $w=0$ and anchors $A_r=0^{2r}$ , $$\lambda(0A_r0)=A_r.$$ Consequently the same raw rope cell $0$ requires infinitely many distinct typed receipt targets as its anchor varies.

Bridge-chasing escape

For $r\geq1$ and $d\geq0$ , let $$P_{r,d}=A_r(11A_r)^d, \qquad A_r=0^{2r}.$$ These are even palindromes. For $d>0$ , $$\lambda(P_{r,d})=P_{r,d-1} \quad\text{and}\quad b_{P_{r,d}}=1,$$ whereas the bridge of $A_r$ is $0$ . The search for the $0$ -transition from $P_{r,d}$ therefore makes exactly $d$ fa…

Bridge-shadow identity

Suppose $H=RbP$ , $\lambda(H)=P$ , and $P$ is the longest even-palindromic suffix of $w^RP$ . If $w=\epsilon$ , or if the first letter of $w$ differs from $b$ , then $$\Lambda(H,w)=\Lambda(P,w).$$

Mirror-prefix lemma

Let $Y$ be a nonempty even palindrome and $c$ a letter. If $D_c(Y)$ is defined, the final palindrome of $\Pi(cD_c(Y)c,\omega_c(Y))$ is $F=Yc\,\omega_c(Y)$ , and $\lambda(F)=Y$ . If $D_c(Y)$ is undefined, the final palindrome of $\Pi(\epsilon,cY)$ is $F=YccY$ , and $\lambda(F)=Y$ . In both cases t…

With $Y=LbB$ as above and $c\ne b$ : if $D_c(Y)$ is defined, write $L=ZcD_c(L)$ ; then $\lambda(ZcL)=L$ . If $D_c(Y)$ is undefined, then $\lambda(LccL)=L$ .

Receipt-rope recurrence

Let $\rho_b$ be the header receipt of $\Omega_b(Y)$ . For $c\ne b$ , $$\Omega_c(Y)= \begin{cases} \text{undefined},&\Omega_c(L)\text{ undefined},\\ \Omega_c(L)\cdot(b,\rho_b)\cdot\operatorname{body}\Omega_b(Y),&\text{otherwise}, \end{cases}$$ and, whenever $Z_c(Y)$ is defined, $$Z_c(Y)=Z_c(L)\cdot(b,\rho_b)\cdot\operatorname{body}\Omega_b(Y).$$…

Full abstract receipt closure

Over a fixed alphabet, a fresh occurrence record, its complete direct/reset rope table, and the updated live context are obtained from old receipts by a fixed number of head, tail, singleton, inject, and catenation operations.

Simultaneous batch compiler

Every transducer of Definition 10.1 whose initial record graph is fixed, finite, immutable, and pointer-closed compiles exactly and letter-synchronously into a finite scaffolding automaton of degree $$d=\max\{1,s+Aq\}$$ and observation/update distance at most $r+1$ . The source transition uses only bounded labelle…

Kaplan–Tarjan [6, Theorem 5.1, p. 592]

(Kaplan–Tarjan [6, Theorem 5.1, p. 592] ). There is a purely functional regular catenable steque whose push, pop, inject, and catenation operations take worst-case constant time and preserve the representation.

Opaque-atom staging

Let a strict purely functional sequence operation, parameterized by a base element type $A$ , use finite constructor tests and a worst-case bounded number of $\mathsf{car}$ , $\mathsf{cons}$ , and $\mathsf{cdr}$ operations. It may inspect the representation’s own pairs, buffers, and recursive child structure…

Whole-client bounded symbolic normalization

Fix a finite immutable record signature. Let one deterministic strict client transition have a uniform bound on calls, constructor tests, loops, recursion, and retained fresh records. Suppose it observes only finite tags, finite nonpointer data, old records reached by bounded rooted addresses, and constructors of or…

Direct palindrome construction

For a persistent sequence implementation satisfying the contract of Section 11.1, the receipt construction recognizes the binary even-palindrome language with a finite scaffolding automaton. If the complete client has source-record bounds $(A_*,q,R_*)$ , it has degree $\max\{1,2+A_*q\}$ and distance at most $R_*+1$…

Direct PEG route

Under the sequence contract in Theorem 12.2, the construction yields a PEG for $\mathsf{EPAL}_2$ .