Theorems

If $m\ne n$ , then $K_m$ and $K_n$ have different complete-match behavior.

State equality preserves every future

If $\delta^*(s_0,u)=\delta^*(s_0,u')$ , then for all $v\in\Sigma^*$ , $$uv\in L(\mathcal A)\quad\Longleftrightarrow\quad u'v\in L(\mathcal A).$$

Regular languages are closed under Boolean operations

If $L_1$ and $L_2$ are recognized by finite DFAs, then so are $L_1\cap L_2$ , $L_1\cup L_2$ , and $\Sigma^*\setminus L_1$ .

Residual recognition

The residual dynamic recognizes $L$ exactly.

Myhill–Nerode theorem, residual form

For a language $L\subseteq\Sigma^*$ , the following are equivalent: $L$ is recognized by a finite DFA; $L$ has finitely many left residuals; the relation $\equiv_L$ has finite index. When these conditions hold, the residual automaton is the unique minimal reachable DFA up to isomorphism.

The composition of continuous maps is continuous.

Finite intersection characterization

A space $X$ is compact if and only if every family of closed sets $\{C_i:i\in I\}$ with the finite intersection property has nonempty total intersection. The finite intersection property means $$C_{i_1}\cap\cdots\cap C_{i_k}\ne\varnothing$$ for every finite subfamily.

Let $X_n$ be a nonempty finite discrete space for every $n\in\N$ . Then $\prod_{n\in\N}X_n$ is compact.

Universal property of the inverse limit

Let $Y$ be a set and suppose maps $f_n:Y\to X_n$ form a compatible cone: $$\rho_{n+1,n}\circ f_{n+1}=f_n \qquad\text{for every }n.$$ There is a unique map $$f:Y\longrightarrow\varprojlim_nX_n$$ such that $\pi_n\circ f=f_n$ for every coordinate projection $\pi_n$ . If the spaces are topological and every $f_n$…

Closedness of compatibility

For continuous maps between Hausdorff spaces, the set of compatible threads is closed in $\prod_n X_n$ .

Finite discrete inverse-limit existence

Let every $X_n$ be a nonempty finite discrete space, with arbitrary bonding maps $\rho_{n+1,n}:X_{n+1}\to X_n$ . Then $\varprojlim_n X_n$ is nonempty.

Contraction fixed point

If $\mathcal B$ is complete and $F$ is a contraction, then $F$ has a unique fixed point. Starting from any $x_0$ , the iterates $x_{n+1}=F(x_n)$ converge to it.

If $F^r$ is a contraction on a complete metric space, then $F$ has a unique fixed point.

Dyck residual classification

The residuals of $D_k$ are precisely $$\{R_s:s\in\{1,\ldots,k\}^*\}\cup\{\varnothing\}.$$ Distinct stacks give distinct residuals.

Fixed-cut state minimum

The minimum number of reachable cut states in a deterministic strict layered recognizer is the number of distinct rows of $C_{m,n}$ .

Unique language from compatible cuts

Every compatible Boolean cut field determines a unique language $$L_C=\{w:C_{|w|,0}(w,\eps)=1\}$$ such that $$C_{m,n}(u,v)=\mathbf 1[uv\in L_C]$$ for every cut. Conversely, every language produces a compatible field.

Global adjacent plateau

If $q_L(N)=q_L(N+1)$ for some $N$ , then $L$ is regular and $Q_N(L)$ is the state set of its minimal residual DFA.

Basic access laws

For every language over a finite alphabet: $a_L(N)$ exists; $a_L(N)$ is nondecreasing in $N$ ; and if $L$ has a reachable $k$ -state DFA, then $a_L(N)\le k-1$ .

Observation-growth gap

If $L$ is nonregular, then $q_L(N)$ is strictly increasing and $$q_L(N)\ge N+2$$ for every $N\ge0$ . Equivalently, if $q_L$ ever fails to increase at an adjacent pair of horizons, then it remains bounded.

Bounded access characterizes regularity

For a language $L$ , the following are equivalent: $$L\text{ is regular} \quad\Longleftrightarrow\quad \sup_N a_L(N)<\infty \quad\Longleftrightarrow\quad a_L(N)\text{ is eventually constant}.$$

Exact access calculus for controlled Dyck presentations

For every finite controlled-Dyck presentation and every horizon $N$ , $$a_{L_M}(N)=\max_{K\in S_N}\alpha_{M,N}(K).$$ The quantity is effectively computable by finite balanced-distance relaxation, the stack recurrence above, and the finite controlled-Dyck shadow quotient. Moreover, $$\boxed{ a_{L_M}(N)\le\max\{1,(N+1)B_M+N\}. }$$…

The linear access certificate is pointwise sharp

For every horizon $N\ge0$ , some finite controlled-Dyck presentation attains the displayed upper bound. For every $N\ge1$ , one can arrange $B_M=2$ and $$a_{L_M}(N)=3N+2=(N+1)B_M+N.$$ The presentation is allowed to depend on $N$ .

Entry diameter is monotone under DFA quotient

For every such morphism, $$B_{M'}^{\mathrm{ent}}\le B_M^{\mathrm{ent}}.$$ Consequently the reachable minimal DFA of one fixed regular language has no larger entry diameter than any DFA recognizing that regular language.

Dyck-trace minimax certificate

For every controlled-Dyck language inside the fixed envelope $D$ , $$a_L(N)\le\max\{1,(N+1)\beta_D(L)+N\}.$$ The number $\beta_D(L)$ depends only on $L$ and the selected Dyck envelope, not on one chosen regular controller.

Balanced residual access lower bound

Every regular controller presenting $L$ satisfies $$B_M^{\mathrm{ent}}\ge\gamma_D(L),$$ and therefore $$\beta_D(L)\ge\gamma_D(L).$$

Entry-context residual lower bound

Every regular controller presenting $L$ satisfies $$B_M^{\mathrm{ent}}\ge\eta_D(L).$$ Consequently $$\boxed{ \beta_D(L)\ge\eta_D(L)\ge\gamma_D(L). }$$

Finite completion-summary saturation

For every controlled-Dyck language, $\eta_D(L)$ is exactly computable from any finite controller presentation by a terminating finite saturation.

Minimax sandwich stopping rule

If $b_M=\eta_D(L)$ , then the supplied presentation attains the global Dyck-trace minimum and $$\beta_D(L)=\eta_D(L)=b_M.$$ Both endpoints are computed by terminating finite procedures.

First-flip lower bound

Every regular controller presenting $L$ satisfies $$B_M^{\mathrm{ent}}\ge\tau_D(L),$$ and therefore $$\beta_D(L)\ge\tau_D(L).$$ Moreover, $\beta_D(L)=0$ exactly for $L=\varnothing$ and $L=D$ .

Punctured-threshold separation

For every $r\ge2$ , $$\boxed{ \tau_D(L_r^\circ)=2 <\gamma_D(L_r^\circ) =\beta_D(L_r^\circ)=2r. }$$

First-component contextual separation

For every $r\ge3$ , $$\boxed{ \tau_D(H_r)=2, \qquad \gamma_D(H_r)=4, \qquad \eta_D(H_r)=\beta_D(H_r)=2(r-1). }$$ In particular, $\beta_D(H_r)>\gamma_D(H_r)$ for $r\ge4$ .

Terminal-descent sewing collapse

For the trace $K_3$ , $$\boxed{\eta_D(K_3)=\beta_D(K_3)=4.}$$ The three-state presentation is state-minimal but not access-optimal.

Exact state/access frontier of $K_3$

(Exact state/access frontier of $K_3$ ). The minimum size of a controller presenting $K_3$ is three, and $$\nu_D(K_3;4)=6.$$ The nondominated state/access pairs are exactly $$\boxed{(3,6)\quad\text{and}\quad(6,4)}.$$

Terminal-descent family law

For every $m\ge2$ , $$\eta_D(K_2)=\beta_D(K_2)=4, \qquad \eta_D(K_m)=\beta_D(K_m)=2(m-1)\quad(m\ge3).$$

Even positional construction

For every even $m$ , an $(m+2)$ -state controller presents $K_m$ at the optimal entry cost $\beta_D(K_m)$ . At $m=4$ it is isomorphic to the six-state controller displayed above.

Exact access radius for square lengths

For every $m\ge0$ , $$a_{L_{\square}}(2m)=(m+1)^2+1, \qquad a_{L_{\square}}(2m+1)=(m+1)^2+2.$$

Exact depth-threshold profiles

Let $D_{k}^{\ge r}$ be the balanced words over $k$ bracket types whose stack height reaches at least $r\ge1$ . Then $$q_{k,r}^{\ge}(N) =1+\sum_{h=0}^{N}k^h +\sum_{h=\max(0,2r-N)}^{r-1}k^h,$$ $$a_{k,r}^{\ge}(N)=\max(2r,N).$$ For the complementary balanced language $D_k^{<r}$ that stays below $r$ ,…

Real-time transfer

Let $L$ be recognized by a finite deterministic strict real-time multitape Turing machine with a fixed positive number of ordinary single-head work tapes. The machine receives one input symbol and makes one global transition per step, has no input-length advice, and performs no post-input computation. Then $$L^R\in\mathsf{PEG}.$$…

$\mathsf{EPAL}_2\in\mathsf{PEG}$ . Hence Conjecture 7 of Loff–Moreira–Reis is false.

Loff–Moreira–Reis

For every language $K$ , $$K\in\mathsf{PEG} \quad\Longleftrightarrow\quad K^R\text{ is decided by a scaffolding automaton}.$$

Fresh initial state

Every finite scaffolding automaton $A$ has an equivalent finite scaffolding automaton $A^\star$ whose initial state occurs only before the first input symbol. The construction preserves acceptance of the empty word and every nonempty word without inserting an input step.

Persistent-stack update

Suppose the old scaffold is strictly backward and satisfies $\mathsf{CleanEmpty}$ . After appending the node specified by the table, the decoded stack at $v^+$ is exactly the result of the selected stack operation. The new scaffold is strictly backward and again satisfies $\mathsf{CleanEmpty}$ .

Parallel persistent stacks

Every deterministic letter-synchronous finite-control machine with a fixed positive number $s$ of stacks, performing at most one push, keep, or pop per stack and per input symbol, is simulated exactly by a degree- $s$ , distance-two scaffolding automaton.

Tape zipper

Every strict real-time $m$ -tape machine is simulated letter-for-letter by a finite-control machine with $2m$ stacks, performing at most one push, keep, or pop on each stack per input symbol.

Strict machine-to-scaffold simulation

Let $M$ be a strict real-time $m$ -tape machine, $m\geq 1$ . There is a scaffolding automaton $A_M$ of degree $2m$ and distance two such that $$L(A_M)=L(M).$$ After every input prefix, the two persistent stacks associated with each tape, together with its scanned symbol in finite control, reconstruct the s…

If $L$ is recognized by a strict real-time multitape machine, then $$L^R\in\mathsf{PEG}.$$ Equivalently, $$\mathsf{rev}(\mathsf{RT\text{-}MTTM})\subseteq\mathsf{PEG}.$$

Strict real time is online constant time

Every language recognized by a strict real-time multitape machine belongs to $\mathsf{Online}(O(1))$ in the sense of Loff–Moreira–Reis Definition 22.

Proper class containment

$$\mathsf{rev}(\mathsf{RT\text{-}MTTM})\subsetneq\mathsf{PEG}.$$

Classical palindrome interface (classical, imported

). There are finite $m,Q,T$ and a total strict real-time $m$ -tape machine $P$ such that, for every $x\in\{0,1\}^*$ , the state reached after exactly $|x|$ transitions is accepting if and only if $x=x^R$ . The statement includes $x=\varepsilon$ : the initial state is accepting.

Even-palindrome identity

For every binary word $x$ , $$x\in\{ww^R:w\in\{0,1\}^*\} \quad\Longleftrightarrow\quad x=x^R\ \text{ and }\ |x|\text{ is even}.$$ The equivalence includes $x=\varepsilon$ .

Reversal invariance

$$(\mathsf{EPAL}_2)^R=\mathsf{EPAL}_2.$$

Parity product

Suppose a strict real-time machine $P$ reports after every prefix $x$ , including the empty prefix, whether $x=x^R$ . Then a strict real-time machine $P_{\mathrm{even}}$ recognizes exactly $\mathsf{EPAL}_2$ .

The even-length binary palindrome language has a parsing expression grammar: $$\boxed{\mathsf{EPAL}_2=\{ww^R:w\in\{0,1\}^*\}\in\mathsf{PEG}.}$$

Conjecture 7 of Loff, Moreira, and Reis [4] is false.

Retuned direct reduction

For every fixed real number $c$ with $0\le c<1/28$ , there is a deterministic polynomial-time mapping that assigns to each $3$ SAT formula $\varphi$ a nonsingular matrix $B\in\mathbb Z^{n\times n}$ , a target $t\in\mathbb Z^n$ , and a radius $r\in\mathbb Q_{>0}$ such that…

Retuned binary soundness

Under the exact conditions above, if equation (10) has a solution $x$ satisfying $$\operatorname{wt}(x)\le4M^{2c}R,$$ then $\varphi$ is satisfiable.

Binary nearest codeword and binary syndrome decoding are NP-hard to approximate within $n^{1/15}$ under deterministic polynomial-time many-one reductions.

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$ .

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

(Loff–Moreira–Reis [12, Theorem 16, p. 21] ). A language $L$ is in $\mathsf{PEG}$ if and only if $L^R$ is decided by some scaffolding automaton.

Future-context full abstraction

For rooted degree- $d$ scaffolds over one working alphabet: equal unfoldings, equality of every finite rooted neighborhood, and deterministic labelled bisimilarity are equivalent; unfolding equivalence is preserved by every common scaffold row and hence by every common continuation; and unequal unfoldings are dist…

Both $\equiv_{\mathrm s}$ and $\equiv_{\mathrm f}$ are stable under a common right suffix of rows.

Minimal residual figure

Every finite rooted scaffold has a canonical finite behavioral figure $M(\mathcal U)$ whose states are $\mathcal R(\mathcal U)$ , whose root is $\mathcal U_{\epsilon}$ , and whose port $i$ sends $\mathcal U_p$ to $\mathcal U_{pi}$ when defined. The physical reachable graph maps onto $M(\mathcal U)$ by…

Generated-chain theorem

Let $S$ be a legally generated chronological scaffold with current top $t$ . Its physical graph and its minimal figure are weakly acyclic. The nodes reachable from $t$ , and the states of the minimal figure, are totally ordered by reachability. Conversely, every finite behaviorally reduced labelled rooted reac…

Regressive navigation

After adjoining a least missing sink to a generated minimal figure and numbering its chain, every port acts regressively. Its port-word transition monoid is a submonoid of the full regressive transformation monoid and is $\mathcal R$ -trivial.

Guarded folds generate bisimilarity

On every finite weakly acyclic deterministic labelled partial port graph, the equivalence generated by elementary guarded folds is exactly the greatest bisimulation equivalence.

Static normal form

Orient each guarded fold toward its quotient. The system terminates and is confluent up to rooted labelled port-graph isomorphism. Its normal form is the minimal residual figure.

Semantic causal sewing

Two strongly equivalent length- $n$ histories are connected by at most $n$ semantic step replacements.

One-state extension dichotomy

Suppose two such fresh roots have the same behavior. If the behavior is not already a state of $Q$ , their missing and $\mathsf{SELF}$ positions agree, and their old target agrees at every other port. If the behavior is an old state $q\in Q$ , each row is a guarded unroll of $q$ : it copies every missing and…

Canonical history exists

Every realizable finite strong trace has a unique lexicographically least history. It is obtained from left to right by appending the least row that realizes the next figure over the already chosen prefix.

Reduced live prefixes

Every root-reachable component at every prefix of a SELF-eager history is behaviorally reduced.

Convergent strong-trace presentation

For fixed finite $d,k,\Gamma$ , oriented endpoint detours and literal guarded unrolls form a terminating confluent graph-local presentation of strong equivalence. Two histories have the same strong trace if and only if they reduce to the same SELF-eager history. A length- $n$ history normalizes in at most $dn$…

Replay invariance

Suppose an equal-length history $H'$ agrees with $H$ on the labels of $R_H$ and on every descriptor cell in $C_H$ . Then the final rooted concrete scaffolds of $H$ and $H'$ are identical. Moreover $R_{H'}=R_H$ and $C_{H'}=C_H$ .

Causal-garbage cube

Every garbage fibre is the Cartesian product of the finite value sets of its unsupported label and descriptor coordinates. Simultaneous $G$ factors into single-coordinate changes. Fill a triangle for three values of one coordinate and a square for changes of two distinct coordinates. The resulting path two-complex…

Unexposed two-row sewing

Fix $d$ , $k\geq1$ , and a behaviorally reduced old prefix. Consider two unexposed acyclic two-row extensions with the same consumer label, the same valid nonmissing path-demanding consumer coordinates, and literal agreement as missing or $\mathsf{SELF}$ on every other consumer coordinate. If corresponding pat…

Unique relay

If consecutive states $u>v$ of that final reduced chain are carried at nonadjacent construction times, the supported descriptor segment between them is, up to endpoint detours at a recursive bottom, $$\epsilon\,0\,0\cdots0.$$

Unary final presentation

Fix a length $n$ , a nonempty finite working alphabet, degree one, and distance one. Two histories have the same final behavioral figure if and only if they are connected by endpoint detours, absorption, causal-garbage changes, and temporal carrier slides. Every final fibre contains one literal right-packed normal…

Carrier-surgery CAT(0

geometry). For a fixed unary distance-one final figure and history length, the temporal slide graph on strong/garbage chambers is the undirected Hasse graph of the order-ideal lattice of the rectangle above. Filling every Boolean family of independent slides gives the CAT(0) cube complex $X(P)$ . If the rectangle…

Simultaneous-batch compiler; fixed virtual initialization

Every bounded simultaneous record transducer with parameters $(s,A,q,r)$ , one fixed finite immutable pointer-closed initial graph, and plans determined by finite control, the input letter and bounded labelled rooted unfoldings has an exact letter-synchronous native scaffolding-automaton implementation of degree $$d=\max\{1,s+Aq\}$$…

Opaque-element staging

Let a strict purely functional sequence operation: use only finite constructor tests and a worst-case bounded number of fixed-arity constructor, projection, and pointer steps; treat elements of its base type as opaque atoms, with no equality, hashing, pattern match, identity test, or traversal through a base element…

Feedback programs compile

Let a persistent program, at each input letter, start from a fixed number $s$ of roots and perform a fixed finite composition of strict purely functional sequence operations satisfying the hypotheses of Theorem 9.4 on opaque pointer elements. In addition it may create a bounded number of fresh fixed-arity records…

Corrected carrier rectangles

For an ordinary missing or base terminal and $m\ge1$ , carrier placements are the ideals of $[m-1]\times[n-m]$ . For a recursive terminal, $m=0$ is a singleton; for $m\ge1$ , placements are the ideals of $[m-1]\times[n-m-1]$ .

Carrier cube

Filling every Boolean family of independent temporal slides gives the rooted CAT(0) order-ideal cube of Proposition 3.1 . For a rectangle with $r$ rows and $c$ columns it has $rc$ hyperplanes, dimension $\min(r,c)$ , edge distance $$d(t,s)=\sum_{i=1}^{r}|t_i-s_i|,$$ and coordinatewise-median carrier tuples.

Unique quotient normal class

Every final fibre has one irreducible garbage class, the right-packed class $\mathsf{RP}_n(F)$ . Hence oriented effective horizontal rewriting terminates and is object-confluent modulo garbage.

Garbage-trivial collapse

If a legal $D$ or $A$ edge is trivial modulo garbage, it equals one descriptor garbage edge. If a legal $T$ edge is trivial modulo garbage, it equals a two-descriptor garbage path; the two orders agree by the garbage square.

Descriptor-support monotonicity

For every effective oriented horizontal move $R$ , $$\operatorname{DescSupp}(RH)\subseteq\operatorname{DescSupp}(H).$$ Every coinitial horizontal/garbage-descriptor branching is therefore a strict naturality square modulo garbage.

Support captures

The only mixed branches without a strict horizontal residual are $$A/GL(0),\qquad T/GL(0),\qquad T/GL(-1).$$ They require no new generator: the garbage-first path returns along the inverse garbage edge and then takes the original reduction, so $G;G^{-1};R=R$ by vertical cancellation.

A/T hexagon

The following paths have exactly the same raw physical endpoint: $$A_y;A_x = T_{yz};A_x;A_y;D_z.$$ No garbage quotient is used in this equation.

Local cell classification

Every coinitial effective horizontal pair is aspherical, Peiffer/cubical, D/A triangular, A/T hexagonal, or D/T derived. Every horizontal/garbage pair is a strict naturality square or one of the three cancellation captures. Every garbage-trivial horizontal edge has a collapse cell from Lemma 4.2 .

Uniform guarded path presentation

Fix a finite alphabet and history length in degree one and distance one. In each final behavioral fibre, all parallel paths generated by endpoint detours, literal absorptions, causal-garbage changes, and temporal slides are presented by the following length-independent guarded cell families: garbage same-coordinate…