\documentclass[11pt]{article} \usepackage[T1]{fontenc} \usepackage[utf8]{inputenc} \usepackage{lmodern} \usepackage[margin=1in]{geometry} \usepackage{amsmath,amssymb,amsthm,mathtools} \usepackage{booktabs,tabularx,array} \usepackage{enumitem} \usepackage{xcolor} \usepackage{microtype} \usepackage{fancyhdr} \usepackage{graphicx} \usepackage{tikz} \usetikzlibrary{arrows.meta,positioning,fit,calc,decorations.pathreplacing} \usepackage{hyperref} \hypersetup{ colorlinks=true, linkcolor=blue!55!black, citecolor=blue!55!black, urlcolor=blue!55!black, pdftitle={Persistent Receipts and Simultaneous Records: A Direct Scaffold for Even Palindromes}, pdfauthor={Joshua Gay} } \urlstyle{same} \setlist{nosep} \setlength{\parskip}{0.45em} \setlength{\parindent}{0pt} \pagestyle{fancy} \fancyhf{} \fancyhead[L]{Direct palindrome scaffolding} \fancyhead[R]{Draft 2, review stage} \fancyfoot[C]{\thepage} \renewcommand{\headrulewidth}{0.3pt} \setlength{\headheight}{14pt} \newtheorem{theorem}{Theorem}[section] \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{corollary}[theorem]{Corollary} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newenvironment{question} {\begin{quote}\itshape\textbf{Guiding question.}\ }{\end{quote}} \newenvironment{intuition} {\begin{quote}\small\textbf{Working picture.}\ }{\end{quote}} \newenvironment{scope} {\begin{quote}\small\textbf{What this does and does not say.}\ }{\end{quote}} \newcommand{\EPAL}{\mathsf{EPAL}_2} \newcommand{\SA}{\mathsf{SA}} \newcommand{\PEG}{\mathsf{PEG}} \newcommand{\eps}{\epsilon} \newcommand{\missing}{\varnothing} \newcommand{\SELF}{\mathsf{SELF}} \newcommand{\MISS}{\mathsf{MISSING}} \newcommand{\tail}{\operatorname{tail}} \newcommand{\body}{\operatorname{body}} \newcommand{\wrap}{\operatorname{wrap}} \newcommand{\Rec}{\operatorname{Rec}} \newcommand{\FAIL}{\mathsf{FAIL}} \newcommand{\car}{\mathsf{car}} \newcommand{\cdr}{\mathsf{cdr}} \newcommand{\cons}{\mathsf{cons}} \newcommand{\emptyrec}{\bot} \tikzset{ box/.style={draw=black!65, rounded corners=2pt, align=center, inner sep=5pt, fill=black!3, font=\small}, emphbox/.style={box, draw=black, fill=black!8}, record/.style={draw=black!70, rectangle, align=center, inner sep=4pt, fill=white, font=\small}, snode/.style={draw=black!80, circle, minimum size=7mm, inner sep=1pt, fill=white, font=\small}, flow/.style={-{Latex[length=2mm]}, semithick, draw=black!75}, dashedflow/.style={flow, dashed}, every picture/.style={line cap=round, line join=round} } \title{\textbf{Persistent Receipts and Simultaneous Records:\\ A Direct Scaffold for Even Palindromes}} \author{Joshua Gay\\\small FPRD Lab, Insight Forge} \date{Draft 2, 22 August 2026} \begin{document} \maketitle \begin{abstract} A parsing expression grammar (PEG) is a grammar read as a deterministic recognition procedure: alternatives are tried in a fixed order and the first success is committed to. Loff, Moreira, and Reis proved that a language has a PEG exactly when its \emph{reversal} is decided by a \emph{scaffolding automaton}, a machine that reads its input once, left to right, and appends one bounded-degree node to a permanent graph at every letter. They conjectured that the language of even-length binary palindromes $\EPAL=\{ww^R:w\in\{0,1\}^*\}$ has no PEG. That conjecture is false, and this paper gives a direct proof: we build a finite scaffolding automaton that recognizes $\EPAL$ and then apply the Loff--Moreira--Reis correspondence. The automaton maintains, for the input read so far, its longest even-palindromic suffix and the reversed context to the left of that suffix. Because a scaffold can never modify an old node, the usual mutable palindrome index (a ``palindromic tree'') is unavailable; we replace its pointers by \emph{typed receipts}---immutable pointers to the particular historical record a later step will need---and transport them in \emph{persistent receipt ropes} built from Kaplan and Tarjan's catenable steques. The construction meets one genuine obstacle: a fresh palindrome record must own a fresh rope whose last cell points back to that record, a cycle no ordinary allocate-then-link discipline can build. We define \emph{bounded simultaneous record transducers}, whose one-step update is an arbitrary finite graph of fresh records, and prove that every such transducer compiles into a scaffolding automaton, using the scaffold's self-reference port together with finite slot tags. A staging theorem explains why the steque's acyclic allocation can be tied to the fresh owner only at that boundary. The membership conclusion is not new: an earlier paper from the same project proves it by compiling a classical real-time Turing-machine recognizer. What is new here is the direct persistent representation and the compiler theorem, which does not depend on palindromes. The paper is written to be checkable from its own text plus the cited literature; it defines grammars, PEGs, scaffolding automata, persistence, and every structure it uses. It is released for specialist review and makes no novelty claim. \end{abstract} \tableofcontents \part{Why this proof looks different} \section{The question and the direct route} \label{sec:question} \begin{question} Can a device that adds only one bounded-local graph node per input letter recognize a language whose obvious description compares two unbounded halves? \end{question} \subsection{The language and the conjecture} Write $w^R$ for the word $w$ read backwards and $\EPAL$ for the set of binary words of the form $ww^R$: the even-length palindromes $\eps$, $00$, $11$, $0110$, $1001$, $001100$, and so on. As a \emph{generative} object the language is as simple as they come: three rewriting rules produce it (Section~\ref{sec:cfg}). Loff, Moreira, and Reis (hereafter LMR) studied how much computational power the \emph{recognition-based} grammars called parsing expression grammars have, and found both surprising positive examples and a natural negative conjecture \cite[Conjecture~7, p.~10]{LMR2020}: \begin{quote} \emph{The language of even-length palindromes has no PEG, i.e.\ $P=\{ww^r\mid w\in\{0,1\}^*\}\notin\mathsf{PEG}$.} \end{quote} The intuition behind the conjecture is that a PEG cannot ``find the middle'' of its input. The conjecture is false. An earlier paper of this project \cite{GayStacks2026} refuted it by compiling strict real-time multitape Turing machines into LMR's scaffolding automata and invoking the classical theorem that palindromes are recognizable in real time by such a machine \cite{Slisenko1977,Galil1978}. That route proves membership but explains nothing about \emph{what a scaffold must remember} to compare two halves. \subsection{What this paper does} This paper gives a second, direct proof. The reader needs no Turing machine and no palindrome theorem: only words, finite graphs, and one inherited data structure. Figure~\ref{fig:two-routes} shows the two routes. \begin{figure}[ht] \centering \resizebox{\textwidth}{!}{% \begin{tikzpicture}[node distance=9mm and 13mm] \node[box] (pal) {$\EPAL$\\even palindromes}; \node[box, right=of pal, yshift=9mm] (rt) {classical real-time\\multitape recognizer\\(Slisenko, Galil)}; \node[box, right=of rt] (transfer) {machine-to-scaffold\\compiler \cite{GayStacks2026}}; \node[box, right=of pal, yshift=-9mm] (receipts) {occurrence receipts\\and persistent ropes\\(this paper)}; \node[box, right=of receipts] (direct) {bounded simultaneous\\record compiler\\(this paper)}; \node[emphbox, right=20mm of $(transfer)!0.5!(direct)$] (sa) {finite scaffolding\\automaton}; \node[emphbox, right=of sa] (peg) {$\EPAL\in\PEG$}; \draw[flow] (pal) -- (rt); \draw[flow] (rt) -- (transfer); \draw[flow] (transfer) -- (sa); \draw[flow] (pal) -- (receipts); \draw[flow] (receipts) -- (direct); \draw[flow] (direct) -- (sa); \draw[flow] (sa) -- node[above, font=\scriptsize]{LMR Thm.~16} (peg); \end{tikzpicture}% } \caption{Two proofs of the same membership statement. The upper route is the earlier transfer proof. This paper develops the lower route. Both end with the same inherited theorem of Loff, Moreira, and Reis.} \label{fig:two-routes} \end{figure} The lower route produces two separable results. \begin{itemize} \item \textbf{The application.} A finite scaffolding automaton recognizes $\EPAL$ (Theorem~\ref{thm:direct}); by LMR's theorem and the fact that $\EPAL$ is its own reversal, $\EPAL\in\PEG$ (Corollary~\ref{cor:peg}). \item \textbf{The reusable tool.} Any one-step update that reads a bounded amount of old persistent structure and creates a bounded finite graph of fresh records---\emph{even a graph with cycles among the fresh records}---can be performed by one scaffold node (Theorem~\ref{thm:compiler}). The palindrome construction is exactly what forces the cyclic case. \end{itemize} \subsection{How to read this paper} Section~\ref{sec:background} defines everything the argument uses: words, context-free grammars, PEGs, scaffolding automata, persistence, and the mutable palindrome index that the scaffold cannot have. A reader who knows these objects may skim it, but should read Definition~\ref{def:scaffolding-automaton} and Theorem~\ref{thm:lmr}, whose exact form matters. Section~\ref{sec:map} fixes three layers of description that the proof keeps separate. Section~\ref{sec:trace} follows one input word by hand. Part~II proves the combinatorics of the longest even-palindromic suffix and turns it into operations on persistent ropes. Part~III defines the compiler, proves it, and assembles the automaton. Part~IV says what was proved, what is inherited, and what remains open. Proofs state their strategy before their details. Every example says which of its features generalize. Theorem statements are complete in this paper; the only external premises are LMR's Theorem~16 (sufficient direction) and Kaplan--Tarjan's Theorem~5.1, both quoted with their hypotheses. \section{Background: words, grammars, parsing expression grammars, and scaffolds} \label{sec:background} \subsection{Words, languages, palindromes} \label{sec:words} An \emph{alphabet} $\Sigma$ is a finite set of letters; in this paper $\Sigma=\{0,1\}$ unless stated otherwise. A \emph{word} is a finite sequence of letters, $\eps$ is the empty word, $\Sigma^*$ is the set of all words, and $|w|$ is the length of $w$. Juxtaposition $uv$ is concatenation. A \emph{language} is any subset of $\Sigma^*$. The \emph{reversal} of $w=c_1c_2\cdots c_n$ is $w^R=c_n\cdots c_2c_1$; reversal of a language is $L^R=\{w^R:w\in L\}$. A word $u$ is a \emph{suffix} of $w$ if $w=xu$ for some $x$, and a \emph{proper} suffix if moreover $u\ne w$; prefixes are defined symmetrically. The empty word is a proper suffix of every nonempty word. A \emph{palindrome} is a word $w$ with $w=w^R$; an \emph{even palindrome} is a palindrome of even length, equivalently a word of the form $ww^R$. The empty word is an even palindrome. Thus \[ \EPAL=\{ww^R:w\in\{0,1\}^*\}=\{\text{even palindromes over }\{0,1\}\}, \] and $\EPAL^R=\EPAL$ because reversing $ww^R$ gives $ww^R$ again. When a palindrome $P$ occurs as a suffix of a word $S=CP$, the letter of $C$ immediately to the left of that occurrence will matter constantly; we say the occurrence is \emph{preceded by} that letter. The empty suffix of a nonempty word is preceded by the word's last letter; the empty suffix of $\eps$ is preceded by no letter. \subsection{Context-free grammars: the generative reading} \label{sec:cfg} A \emph{context-free grammar} consists of a finite set of terminal symbols (our alphabet), a disjoint finite set of non-terminal symbols, a start non-terminal, and finitely many \emph{rewriting rules} $A\to\varphi$ in which $A$ is one non-terminal and $\varphi$ is a word over terminals and non-terminals \cite[pp.~120--122]{ChomskySchutzenberger1963}. A \emph{derivation} starts from the start symbol and repeatedly replaces one occurrence of a non-terminal by the right-hand side of one of its rules, in any order, until only terminals remain. The language \emph{generated} by the grammar is the set of terminal words obtained by some derivation. \begin{example}[even palindromes are context-free] \label{ex:cfg-pal} With start symbol $S$ and rules \[ S\to 0S0,\qquad S\to 1S1,\qquad S\to\eps, \] the derivation $S\Rightarrow 0S0\Rightarrow 01S10\Rightarrow 0110$ produces $0110$, and in general the generated language is exactly $\EPAL$: each rule adds one matching letter at each end, and every $ww^R$ arises by choosing the letters of $w$ in order. The reading is \emph{existential}: a word belongs to the language if \emph{some} sequence of choices produces it. Nothing in the definition says how a machine would discover those choices. \end{example} \subsection{Parsing expression grammars: the recognition reading} \label{sec:peg} Parsing expression grammars, introduced by Ford \cite[\S3]{Ford2004}, use rule shapes that look like context-free rules but give them an operational meaning. We follow the formalization of LMR \cite[Definitions~1--4]{LMR2020}, which is the one their theorem is stated for. \begin{definition}[parsing expressions and grammars] \label{def:peg} Fix disjoint finite sets $\Sigma$ of terminals and $\mathit{NT}$ of non-terminals. \emph{Parsing expressions} are built from the atoms $a\in\Sigma$, $A\in\mathit{NT}$, $\varepsilon$ (accept the empty word) and $\FAIL$ by three constructions: \emph{sequence} $e_1e_2$, \emph{ordered choice} $e_1/e_2$, and the \emph{predicates} $!e$ and $\&e$. A \emph{parsing expression grammar} $G$ assigns to each non-terminal $A$ one expression $R(A)$, written $A\leftarrow R(A)$, and names a start non-terminal $S$. \end{definition} The meaning of an expression is a \emph{recognition procedure} $\Rec_G(e,x)$ that reads an input word $x$ from the left and either \emph{fails} or \emph{succeeds consuming a prefix} $x'$ of $x$ \cite[Definition~3 and Algorithm~1]{LMR2020}: \begin{itemize} \item $\varepsilon$ succeeds consuming nothing; $\FAIL$ fails; the terminal $a$ succeeds consuming $a$ if $x$ begins with $a$, and fails otherwise. \item Sequence $e_1e_2$: run $e_1$ on $x$; if it succeeds consuming $y_1$, run $e_2$ on the remainder; succeed consuming $y_1y_2$ if both succeed, otherwise fail. \item Ordered choice $e_1/e_2$: run $e_1$; \emph{if it succeeds, that is the answer}; only if it fails is $e_2$ run on the same input. \item Predicates: $!e$ succeeds consuming nothing if $e$ fails, and fails if $e$ succeeds; $\&e$ succeeds consuming nothing if $e$ succeeds. \item A non-terminal $A$ runs $R(A)$. \end{itemize} The procedure is deterministic: at every point exactly one thing happens. It may loop forever (for example $A\leftarrow A$); a grammar is \emph{total} if it never does. Following LMR, a total grammar \emph{recognizes} the language \[ L(G)=\{x\in\Sigma^*:\Rec_G(S,x)=x\}, \] the words on which the start expression succeeds \emph{consuming the whole input}, and $\PEG$ is the class of languages recognized by total PEGs \cite[Definition~4]{LMR2020}. We call this \emph{complete-match} recognition; it is the ordinary notion, not a variant. \begin{example}[order is semantic] \label{ex:order} Take $S\leftarrow a/ab$ and the input $ab$. The first alternative $a$ succeeds consuming $a$, so the choice commits to it: $\Rec(S,ab)=a\ne ab$, and $ab\notin L(G)$ although the second alternative would have consumed it. As a context-free grammar, $S\to a\mid ab$ generates $\{a,ab\}$. Ordered choice is not a parsing strategy for a context-free grammar; it changes the language. (Ford proves the corresponding algebraic fact: sequence distributes over ordered choice on one side only \cite[p.~7]{Ford2004}.) \end{example} \begin{example}[predicates see ahead without consuming] The expression $!(0/1)$ succeeds exactly at the end of the input, consuming nothing, because it succeeds only where no letter can be read. Predicates let a PEG test a property of the remaining input and then parse it again. It is known that the non-context-free language $\{a^nb^nc^n\}$ has a PEG \cite[p.~3, citing Aho and Ullman]{LMR2020}, and LMR use predicates to recognize the palindromes of power-of-two length \cite[Theorem~8, p.~10]{LMR2020}. \end{example} \subsection{Why comparing the two classes is not a syntactic matter} \label{sec:cfg-vs-peg} Example~\ref{ex:cfg-pal} shows $\EPAL$ is context-free by three rules. One cannot read those rules as a PEG and hope: the choice $S\leftarrow 0S0/1S1/\varepsilon$ commits to $0S0$ whenever the input begins with $0$, and then must find the matching closing $0$ at a position it has no way to locate---a PEG consumes left to right and cannot ``count to the middle''. That is the content of LMR's conjecture. Conversely, PEGs recognize languages, such as $\{a^nb^nc^n\}$ \cite[p.~3]{LMR2020}, that no context-free grammar generates. Neither class contains the other by any syntactic argument; the comparison must go through a machine model. LMR supplied that model. \subsection{Scaffolding automata} \label{sec:scaffold} LMR's machine builds a permanent graph. We give their definition \cite[Definitions~10--15, pp.~14--16]{LMR2020} in words first, then precisely, then with a picture. In words: the machine reads one input letter at a time. Its memory is a growing directed graph whose nodes are numbered $0,1,2,\ldots$ in the order of creation; node $0$ is an unlabelled base, and every later node carries a label from a finite \emph{working alphabet} and a fixed number $d$ of \emph{ports} (outgoing edges), each pointing to an older node, to the node itself, or to nothing. Old nodes are never changed. At each letter the machine looks only at the nodes within a fixed distance $k$ of the most recently created node (the \emph{top}), following ports; based on what it sees, on the letter, and on its finite control state, it creates one new node, chooses its label, and chooses where its ports point---necessarily among the nodes it just looked at, or the new node itself. After the last letter it accepts or rejects by its control state. \begin{definition}[scaffold] \label{def:scaffold} Let $d\ge1$ and let $\Gamma$ be a finite alphabet. A $(d,\Gamma)$-scaffold with top $t$ has nodes $0,1,\ldots,t$, a label $L(v)\in\Gamma\cup\{\missing\}$ for each node ($L(0)=\missing$: the base is unlabelled), and for each node $v$ and each port $i\in\{0,\ldots,d-1\}$ a target $e_v(i)\in\{0,\ldots,v\}\cup\{\missing\}$ (\emph{edges point backwards or to the node itself}; $\missing$ means the port is missing). A \emph{port word} $p=p_1\cdots p_m$ over $\{0,\ldots,d-1\}$ is followed from a node by taking port $p_1$, then port $p_2$ of the node reached, and so on; it is \emph{valid} from $v$ if no missing port is met, and then it has an \emph{endpoint}. The $k$-\emph{neighbourhood} $N_k(v)$ of a node is the labelled tree of depth $k$ obtained by unfolding ports from $v$: it records the label of every node reached by a port word of length at most $k$, and where a port is missing. The tree records labels, not node numbers, so it does not reveal whether two port words reach the same node. \end{definition} \begin{definition}[scaffolding automaton] \label{def:scaffolding-automaton} A scaffolding automaton is a tuple $A=\langle\Sigma,d,\Gamma,k,Q,\delta,q_0,F\rangle$: an input alphabet $\Sigma$, a degree $d\ge1$, a working alphabet $\Gamma$, a distance $k\ge0$, a finite set of control states $Q$ with initial state $q_0$ and accepting states $F\subseteq Q$, and a transition function \[ \delta:\ Q\times\Sigma\times N_k(d,\Gamma)\longrightarrow Q\times\Gamma\times\bigl(\{0,\ldots,d-1\}^{\le k}\cup\{\SELF,\missing\}\bigr)^d , \] where $N_k(d,\Gamma)$ is the set of possible $k$-neighbourhoods. The computation on $x=\sigma_1\cdots\sigma_n$ starts from the scaffold consisting of the base node alone and the state $q_0$. At step $j$ the machine computes $(q',\gamma,p_0,\ldots,p_{d-1})=\delta(q,\sigma_j,N_k(t))$, where $t$ is the current top, and appends node $t+1$ with label $\gamma$ and ports \[ e_{t+1}(i)=\begin{cases} \text{the endpoint of }p_i\text{ followed from }t,&p_i\text{ a valid port word},\\ \missing,&p_i=\missing\text{ or }p_i\text{ invalid},\\ t+1,&p_i=\SELF. \end{cases} \] The new state is $q'$. The word is accepted if the state after the last letter lies in $F$; $L(A)$ is the set of accepted words, and we write $L\in\SA$ when some scaffolding automaton decides $L$. \end{definition} Three points deserve emphasis. The descriptor $\eps$ (the empty port word) names the old top itself. The descriptor $\SELF$ lets a new node point to itself; it is part of LMR's model, not an extension. And the machine cannot test whether two observed nodes are the same node: it sees a tree. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=14mm] \node[snode, fill=black!8] (n0) {$0$}; \node[snode, right=of n0] (n1) {$1{:}a$}; \node[snode, right=of n1] (n2) {$2{:}b$}; \node[snode, right=of n2] (n3) {$3{:}a$}; \draw[flow] (n1) -- node[above,font=\scriptsize]{$0$} (n0); \draw[flow] (n2) -- node[above,font=\scriptsize]{$0$} (n1); \draw[flow, bend left=35] (n2) to node[below,font=\scriptsize]{$1$} (n0); \draw[flow, bend right=35] (n3) to node[above,font=\scriptsize]{$1$} (n1); \draw[flow] (n3) to[out=60,in=0,looseness=6] node[right,font=\scriptsize]{$0$} (n3); \node[box, right=12mm of n3, align=left, font=\scriptsize, text width=52mm] (tree) {$N_2(3)$ as a tree: root $a$;\\ port 0 $\to a$ (port 0 $\to a$, port 1 $\to a$);\\ port 1 $\to a$ (port 0 $\to$ unlabelled, port 1 missing)}; \end{tikzpicture} \caption{A scaffold of degree $2$ after three letters. Node $1$ was created with descriptors $(\eps,\missing)$ from top $0$; node $2$ with $(\eps,0)$ from top $1$ (port $1$ follows port word $0$ from node $1$ and reaches node $0$); node $3$ with $(\SELF,0)$ from top $2$. The depth-$2$ neighbourhood of node $3$ is the tree on the right: it does not record that port $0$ returns to node $3$ itself.} \label{fig:scaffold-example} \end{figure} \subsection{The exact correspondence with PEGs, and why reversal appears} \label{sec:lmr-theorem} \begin{theorem}[Loff--Moreira--Reis {\cite[Theorem~16, p.~21]{LMR2020}}] \label{thm:lmr} A language $L\subseteq\Sigma^*$ is in $\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. \end{theorem} We use only the second sentence (the ``sufficient direction'', whose proof in LMR begins on p.~23). The reversal is not an accident of notation. A scaffolding automaton consumes the input left to right and commits at each letter; LMR's grammar for the reverse language re-enacts the automaton's run from the grammar's point of view, which reads the other way. For a language equal to its own reversal, such as $\EPAL$, the distinction disappears, and this is exactly why Corollary~\ref{cor:peg} mentions reversal invariance. The paper does not use the other direction of the theorem and makes no statement about the class $\SA$ as a whole. \subsection{Persistent data structures} \label{sec:persistence} A data structure is \emph{ephemeral} if an update destroys the old version, and \emph{persistent} if every old version remains available after updates; it is \emph{fully} persistent if old versions can also be updated \cite[\S1]{DSST1989}. The scaffold of Definition~\ref{def:scaffold} is persistent by construction: nothing is ever overwritten. The data structures of this paper are persistent in the strongest sense, which Kaplan and Tarjan call \emph{purely functional}: built only from the three LISP primitives $\cons$ (make a pair), $\car$ and $\cdr$ (read its two components), with no mutation and no memoization \cite[p.~578, footnote~1]{KT1999}. The key consequence is \emph{structural sharing}. If a list is represented as a chain of pairs, then $\cons(x,\ell)$ creates one new pair pointing at the old chain $\ell$; the old list and the new list share everything but that pair, and neither can tell (Figure~\ref{fig:sharing}). A structure that needs to ``copy'' an unbounded old part can instead point to it. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=9mm] \node[record] (a) {$x_1$}; \node[record, right=of a] (b) {$x_2$}; \node[record, right=of b] (c) {$x_3$}; \node[right=of c] (e) {$\cdot$}; \node[record, above left=6mm and 2mm of a] (w) {$y$}; \draw[flow] (a) -- (b); \draw[flow] (b) -- (c); \draw[flow] (c) -- (e); \draw[flow] (w) -- (a); \node[left=3mm of a, font=\scriptsize] {$\ell$}; \node[left=3mm of w, font=\scriptsize] {$\cons(y,\ell)$}; \end{tikzpicture} \caption{Structural sharing. Both lists exist; the new one reuses the old chain.} \label{fig:sharing} \end{figure} A \emph{steque} (stack-ended queue) is a sequence supporting \emph{push} (add at the front), \emph{pop} (remove the front element), and \emph{inject} (add at the rear); a \emph{catenable} steque also supports concatenating two steques \cite[pp.~578--579]{KT1999}. A data structure is \emph{real-time} when every operation takes worst-case constant time---a constant number of primitive steps regardless of the sequence's length \cite[p.~579]{KT1999}. (The reader should keep this \emph{data-structure} sense of ``real-time'' apart from the \emph{machine} sense used in the earlier transfer paper, where a real-time Turing machine is one that performs a bounded number of steps per input letter.) Section~\ref{sec:staging} quotes the theorem of Kaplan and Tarjan that supplies a purely functional real-time catenable steque. \subsection{The mutable palindrome index, and why a scaffold cannot have it} \label{sec:eertree} Algorithms that maintain all palindromes of a growing word use a \emph{palindromic tree} (the \emph{eertree} of Rubinchik and Shur \cite[\S2.2]{RubinchikShur2018}): one node per distinct palindrome, a \emph{suffix link} from each node to its longest proper palindromic suffix, and, added whenever it is first discovered, an edge labelled $c$ from the node of $P$ to the node of $cPc$. Discovering that edge means walking suffix links from the current node until a node is found whose occurrence is preceded by $c$; the walk can be long, but its cost is amortized and the edge is then stored \emph{at the old node}, so it is never needed again. A scaffold can do neither thing. It cannot walk an unbounded chain within one step (it sees distance $k$), and it cannot add an edge to an old node. The present paper shows what must be stored instead: not a pointer from a palindrome \emph{type} to a type, but a pointer carried by each \emph{occurrence} to the particular historical record that the next step will need. Section~\ref{sec:representation-failures} records, with small counterexamples, why each cheaper idea fails. \section{A reader's map} \label{sec:map} \subsection{The viewpoint behind the paper} This paper builds directly on LMR's framework. Their scaffolding automata turn the history generated by a finite transition table into an explicit persistent graph, and their correspondence turns acceptance of that graph process into a PEG language. Our question is therefore not only \emph{whether} $\EPAL$ has some PEG, but \emph{which internal recognition dynamic} makes palindrome comparison visible to that correspondence. Finitely Presented Recognition Dynamics, abbreviated FPRD, is the research viewpoint used in this work: a finite grammar or machine description is treated as a \emph{presentation} that generates an internal recognition \emph{dynamic}, and the accepted language is treated as one \emph{observation} of that dynamic. FPRD Lab is the AI-assisted research project in which the present arguments were developed; nothing in this paper requires trust in that project, its tools, or its records, and Section~\ref{sec:assurance} states plainly what was checked by whom. The viewpoint has one concrete role in the proofs: we keep the \emph{word-level} recurrence (what is true of the input), the \emph{record-level} representation (what a persistent program stores), and the \emph{scaffold-level} encoding (what the machine physically appends) as three separate layers, and we prove each implication between them rather than identifying them. \subsection{Three representations of one state} \begin{description}[style=nextline,leftmargin=0pt] \item[Word state.] For the prefix $S$ already read, we factor $S=CP$ where $P$ is its longest even-palindromic suffix and retain $\ell=C^R$. This level contains ordinary words and exact identities. \item[Persistent record state.] Palindrome occurrences, typed suffix-link receipts, and receipt ropes expose exactly the historical objects needed by the next transition. Sharing occurs here; a stored receipt is a pointer to a particular record, not merely the name of a palindrome string. \item[Physical scaffold state.] A single physical node tuple-packs all logical records born at one input time. A logical pointer is decoded as a physical historical node plus a finite slot tag. \end{description} The distinction between \emph{type} and \emph{occurrence} is especially important. The word $0110$, for example, is one palindrome type. During an online run it may occur at many positions and under different surrounding contexts. A conventional mutable index attaches transitions to the shared type. An immutable scaffold cannot retroactively add a pointer to an old record, so it transports receipts associated with the occurrence that made a transition available. One consequence should be said at once, because it resolves an apparent tension later: the \emph{content} stored in a record (its suffix link, its bridge letter, its ropes) is a function of the palindrome type alone---the receipt traces of Section~\ref{sec:ropes} are defined from words---so any record of the right type would do \emph{semantically}; what depends on the occurrence is only \emph{which} physical record is reachable within the machine's fixed distance. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=8mm and 11mm] \node[box] (factor) {exact factorization\\$S=CP$, $\ell=C^R$}; \node[box, right=of factor] (rec) {three-case longest-suffix\\recurrence}; \node[box, right=of rec] (receipt) {typed mirror receipts\\and receipt ropes}; \node[box, below=of receipt] (steque) {bounded catenable\\sequence operations}; \node[box, left=of steque] (batch) {simultaneous finite\\record batch}; \node[box, left=of batch] (scaffold) {one physical\\scaffold node}; \node[emphbox, below=of batch] (result) {$\EPAL\in\SA$\\and hence $\EPAL\in\PEG$}; \draw[flow] (factor) -- (rec); \draw[flow] (rec) -- (receipt); \draw[flow] (receipt) -- (steque); \draw[flow] (steque) -- (batch); \draw[flow] (batch) -- (scaffold); \draw[flow] (scaffold) |- (result); \end{tikzpicture} \caption{The proof dependency ladder. The upper row is word combinatorics; the lower row is representation and compilation. Executable checks in the public package test individual arrows but are not used as proofs of them.} \label{fig:dependency-ladder} \end{figure} Definitions are given at the first point where they carry proof weight, and Appendix~\ref{app:notation} collects the notation. In diagrams a solid arrow is a logical pointer or implication; a dashed arrow is a decoded or represented relationship rather than an additional heap edge. \section{A running palindrome trace} \label{sec:trace} Before introducing the record machinery, we follow one word. For every input prefix $S$, let $P=P(S)$ be its longest even-palindromic suffix (it exists, since $\eps$ is one), write $S=CP$, and let $\ell=C^R$. The pair $(P,\ell)$ determines acceptance: $\ell=\eps$ exactly when the entire prefix is an even palindrome. It also contains enough word-level information to determine the next pair. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=5mm] \node[record, minimum width=28mm] (c) {$C$}; \node[record, minimum width=36mm, right=0pt of c] (p) {$P=P^R$}; \node[below=6mm of c] (ell) {$\ell=C^R$}; \draw[flow] (c.south) -- ++(0,-3mm) -| (ell.west); \draw[decorate, decoration={brace, amplitude=5pt, mirror}, yshift=-2mm] (c.south west) -- node[below=6mm] {$S=CP$} (p.south east); \node[box, right=12mm of p] (test) {$\ell=\eps$\\iff $S=P$\\iff $S\in\EPAL$}; \draw[flow] (p) -- (test); \end{tikzpicture} \caption{The occurrence-context factorization. The context is reversed so that the letter immediately preceding the current occurrence of $P$ is at the front of $\ell$.} \label{fig:factorization} \end{figure} Table~\ref{tab:running-trace} gives the complete trace for $00011001$. The empty word is displayed as $\eps$. ``External'' means that the new letter matches the first letter of the stored context, so it wraps the entire current palindrome. ``Internal'' means that the full $P$ cannot be wrapped, but a proper even-palindromic suffix of $P$ can. ``Reset'' means that no even suffix at all---not even the empty one---can be wrapped, so the new longest even suffix is empty. Recall that the empty suffix of a nonempty word counts as preceded by the word's last letter; that is why row 3 is an internal update and not a reset. \begin{table}[ht] \centering \small \setlength{\tabcolsep}{3.5pt} \begin{tabular}{@{}rlllllll@{}} \toprule $i$ & old $S$ & $a$ & old $P$ & old $\ell$ & case & new $P$ & new $\ell$ \\ \midrule 1 & $\eps$ & 0 & $\eps$ & $\eps$ & reset & $\eps$ & 0 \\ 2 & 0 & 0 & $\eps$ & 0 & external& 00 & $\eps$ \\ 3 & 00 & 0 & 00 & $\eps$ & internal& 00 & 0 \\ 4 & 000 & 1 & 00 & 0 & reset & $\eps$ & 1000 \\ 5 & 0001 & 1 & $\eps$ & 1000 & external& 11 & 000 \\ 6 & 00011 & 0 & 11 & 000 & external& 0110 & 00 \\ 7 & 000110 & 0 & 0110 & 00 & external& 001100 & 0 \\ 8 & 0001100 & 1 & 001100 & 0 & internal& 1001 & 1000 \\ \bottomrule \end{tabular} \caption{Exact occurrence-context trace for $00011001$. The accompanying checker computes the same eight case labels from the definitions. The table illustrates the recurrence; it is not evidence in place of its proof.} \label{tab:running-trace} \end{table} Two rows are worth pausing over. After the second letter the word is $00$, so $P=00$ and the context is empty: the recognizer would accept at that point. The next $0$ cannot externally wrap $00$, because there is no letter to its left. Nevertheless the empty proper suffix can be internally wrapped, giving the new longest even suffix $00$ at the last two positions and context $0$. At the final row, the current $P=001100$ is preceded by $0$, not by the arriving $1$. The proper suffix $00$ is preceded inside $P$ by $1$, so it is wrapped to $1001$; the remainder of the old palindrome is transferred into the context. That apparent nonlocal jump is the update that the receipt machinery must make bounded-local. The case sequence \[ \text{reset, external, internal, reset, external, external, external, internal} \] will reappear when we interpret the general recurrence. This word will be followed through every layer of the paper: its row 8 becomes the rope update of Example~\ref{ex:row8-ropes} and the scaffold batch of Example~\ref{ex:row8-batch}. What generalizes from it is the three-way case split and the use of the empty suffix; what is incidental is the particular word. \part{Persistent palindrome state} \section{The occurrence-context recurrence} \label{sec:recurrence} \begin{question} What is the smallest exact word state from which one new letter determines the next longest even-palindromic suffix? \end{question} Maintaining a longest suffix is reminiscent of a failure-link automaton (a string-matching automaton whose ``failure'' transitions fall back to the longest matching proper suffix): when the current candidate cannot be extended, one tries a proper suffix. The difference here is that we cannot follow an unbounded chain during one input step. We therefore separate the combinatorial recurrence from the later question of how its selected transition is exposed by one bounded pointer. This section proves the recurrence with ordinary words only. \subsection{Definitions} Let $S$ be the input prefix read so far. Let $P(S)$ be its longest even-palindromic suffix and write \[ S=CP,\qquad \ell=C^R. \] The word $\ell$ is the left-context stack of the current occurrence; its first letter lies immediately to the left of $P$. \begin{definition}[selected suffix and displaced chunk] \label{def:D-omega} For an even palindrome $P$ and a letter $a$, let $D_a(P)$ be the longest proper even-palindromic suffix $Q$ of $P$ for which \[ P=ZaQ \] for some word $Z$ (that is, the longest proper even-palindromic suffix \emph{preceded by $a$} inside $P$), and put $\omega_a(P)=Z^R$. Both are undefined when no such factorization exists. \end{definition} The pair $(D_a(P),\omega_a(P))$ should be read as a factored transition. Its first coordinate is the longest proper suffix of $P$ that the arriving $a$ can wrap. Its second coordinate is exactly the material displaced from the palindrome into the reversed context when that transition is taken. It is important that $D_a(P)$ is selected by an occurrence of $a$ immediately before the suffix, not merely by equality of palindrome types. \begin{definition}[suffix link, bridge, bridge block] \label{def:suffix-link} For a nonempty even palindrome $P$, let $\lambda(P)$ be its longest proper even-palindromic suffix (possibly $\eps$), called its \emph{suffix link}. Write $P=RbL$ with $L=\lambda(P)$; the letter $b$ is the \emph{bridge} of $P$ and $B_P=R^R$ is its \emph{bridge block}. Because $P$ and $L$ are palindromes, $P=P^R=L^Rb^{}R^R=LbR^R$, so $L$ is also a prefix of $P$ and \[ P=RbL=LbB_P . \] At the word level we set $\lambda(\eps)=\eps$ by convention. At the record level, the typed receipt for this empty word is a distinguished empty record $\emptyrec$, which has no suffix-link field or bridge. Thus an occurrence of $\lambda(\eps)$ in a word equation means $\eps$, while the same value stored in a receipt slot is represented by $\emptyrec$. \end{definition} \begin{example} For $P=001100$: $\lambda(P)=00$, the bridge is $b=1$ (the letter before the suffix occurrence of $00$), $R=001$, and $B_P=100$; indeed $P=001\cdot1\cdot00=00\cdot1\cdot100$. For $P=0110$: $\lambda(P)=\eps$, $b=0$ (the last letter), $R=011$, $B_P=110$. For $P=00$: $\lambda(P)=\eps$, $b=0$, $B_P=0$. \end{example} \subsection{The three-case update} \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=4mm and 5mm, font=\small] \node[box, minimum width=42mm, minimum height=29mm] (ext) {}; \node[above=1mm of ext.north] {\textbf{external match}}; \node at ($(ext.center)+(0,5mm)$) {$S=C'aP$}; \node at (ext.center) {$Sa=C'\,aPa$}; \node at ($(ext.center)+(0,-6mm)$) {$\ell=a\ell_0\mapsto\ell_0$}; \node[box, minimum width=48mm, minimum height=29mm, right=of ext] (int) {}; \node[above=1mm of int.north] {\textbf{internal direct}}; \node at ($(int.center)+(0,5mm)$) {$P=ZaD_a(P)$}; \node at (int.center) {$P'=aD_a(P)a$}; \node at ($(int.center)+(0,-6mm)$) {$\ell\mapsto Z^R\ell$}; \node[box, minimum width=42mm, minimum height=29mm, right=of int] (reset) {}; \node[above=1mm of reset.north] {\textbf{reset}}; \node at ($(reset.center)+(0,5mm)$) {$D_a(P)$ undefined}; \node at (reset.center) {$P'=\eps$}; \node at ($(reset.center)+(0,-6mm)$) {$\ell\mapsto aP\ell$}; \end{tikzpicture} \caption{The exhaustive three-case update at the word level. The external case consumes one context letter; the internal case prepends a selected chunk; the reset case moves the entire failed candidate into the context.} \label{fig:three-cases} \end{figure} \begin{theorem}[Occurrence-context factorization] \label{thm:context} 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] (\eps,aP\ell), &\ell\notin a\Sigma^*,\ D_a(P)\text{ undefined}. \end{cases} \] Moreover, \[ S\in\EPAL\quad\Longleftrightarrow\quad \ell=\eps. \] \end{theorem} \begin{proof} \emph{Strategy.} Every new even-palindromic suffix must end with the new letter and therefore begin with it; peel the two copies of $a$ off and what remains is an old even-palindromic suffix preceded by $a$. Then maximize. Every nonempty even-palindromic suffix of $Sa$ has the form $aQa$, where $Q$ is an even-palindromic suffix of $S$ immediately preceded by $a$. If the current longest suffix $P$ is externally preceded by $a$, then $Q=P$ is maximal. Removing that external letter removes the first symbol of $\ell$. Otherwise every eligible $Q$ is a proper suffix of $P$, so maximality selects $D_a(P)$. Writing $P=ZaD_a(P)$ shows that the new context is $CZ$ and hence has reversal $Z^RC^R=\omega_a(P)\ell$. If no eligible proper suffix exists, the longest even suffix is empty and the reversed full prefix is $aP\ell$. Finally $\ell$ is empty exactly when $C$ is empty, which is exactly when the whole prefix equals its longest even-palindromic suffix. \end{proof} In Table~\ref{tab:running-trace}, rows 2, 5, 6, and 7 are external matches; rows 3 and 8 are internal-direct updates; rows 1 and 4 are resets. The final equivalence in the theorem explains why row 2 is accepting and the final row is not. The theorem also shows why keeping only the length of $P$ would be insufficient: the internal case must identify a particular suffix and the chunk that precedes it. \begin{example}[the two internal rows] At row 3 the old palindrome is $P=00$ and the context is empty. For the arriving $0$, the only eligible proper even suffix is $D_0(P)=\eps$. Writing $P=Z0D_0(P)$ gives $Z=0$ and $\omega_0(P)=0$. Hence $P'=0\eps0=00$ and $\ell'=0\eps=0$. The palindrome type has not changed, but its occurrence has: it now occupies the last two positions of $000$ rather than all of the preceding prefix. This is a small example of why occurrence context cannot be discarded. At row 8 the old state is $S=0001100=0\cdot001100$, $P=001100$, $\ell=0$. The arriving letter is $1$, so the external case fails. The factorization $P=001\cdot1\cdot00$ shows $D_1(P)=00$ and $\omega_1(P)=100$. The recurrence gives $P'=1\cdot00\cdot1=1001$ and $\ell'=100\cdot0=1000$. The extra $1$ in $Z=001$ is easy to omit when the factorization is read by eye; reversal then makes that omission visible at the front of the new context. \end{example} \subsection{The transition table has fixed width} \begin{lemma}[chunk recursion] \label{lem:chunk} 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=\eps$ the right-hand sides are undefined). \end{lemma} \begin{proof} Every proper even-palindromic suffix of $P$ is a suffix of $L$, since $L$ is the longest one. The suffix $L$ itself is preceded by $b$, so $D_b(P)=L$ and the displaced chunk is $R^R=B_P$. For $a\ne b$, the suffix $L$ is not eligible, so every eligible suffix is a proper suffix of $L$ preceded by $a$ \emph{inside $L$}, which is the definition of $D_a(L)$; writing $L=Z'aD_a(L)$ gives $P=RbZ'aD_a(L)$, so $\omega_a(P)=(RbZ')^R=Z'^R\,b\,R^R=\omega_a(L)\,b\,B_P$. \end{proof} \begin{example} For $P=001100$ ($L=00$, $b=1$, $B_P=100$): $D_1(P)=00$, $\omega_1(P)=100$; and $D_0(P)=D_0(00)=\eps$, $\omega_0(P)=\omega_0(00)\cdot1\cdot100=0\cdot1\cdot100=01100$. Directly, $P=00110\cdot0\cdot\eps$ and $(00110)^R=01100$. \end{example} This recursion is the first sign of persistent self-similarity. For the one letter $b$ immediately before the suffix link, the desired transition is available at the current record. Every other alphabet coordinate is inherited from the suffix-link record and receives the same intervening block. Because the alphabet is fixed, the entire transition table has fixed width. The remaining difficulty is not the number of coordinates; it is transporting the correct historical record and the potentially long intervening word without walking through either one. \section{Typed mirror receipts} \label{sec:receipts} Theorem~\ref{thm:context} reduces online recognition to catenating type-indexed chunks. It does not yet say how a fresh occurrence obtains its suffix-link record without a search. The needed object is a typed receipt. A palindrome \emph{type} is a word such as $001100$. A palindrome \emph{occurrence} is that word at a specified interval of the input history. The distinction is inexpensive in the mutable palindromic tree of Section~\ref{sec:eertree}: a dictionary may map a type and a letter to another type whenever the transition is discovered. An append-only scaffold has no such global update. The record available at the current top must already carry a bounded route to the historical occurrence that will certify its next suffix link. The word ``typed'' in \emph{typed receipt} does not mean a programming-language type annotation. It means that the receipt identifies a record of exactly the palindrome type required by the proof. A raw time coordinate says where some relevant substring ended; a typed receipt says which immutable record at that history node represents the required suffix-link occurrence. \begin{theorem}[Typed mirror receipt] \label{thm:mirror} 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},\\ \eps,&D_a(Q)\text{ undefined}. \end{cases} \] The palindrome $\lambda(Y)$ has a complete occurrence in the old input and a pre-existing birth record. One old typed pointer can therefore install the suffix-link field of $Y$. \end{theorem} \begin{proof} Every proper nonempty even-palindromic suffix of $Y=aQa$ is $aRa$, where $R$ is a proper even-palindromic suffix of $Q$ immediately preceded in $Q$ by $a$. Maximizing $R$ gives the displayed formula. Since $Y$ is a palindrome, $\lambda(Y)$ is also a proper prefix of $Y$; that prefix ends before the newly appended final $a$, so the complete occurrence lies in the old input. At the first occurrence of any nonempty even palindrome $H$, it is the longest even-palindromic suffix of the prefix ending there. Otherwise a longer even-palindromic suffix would contain $H$ as a proper prefix as well as a suffix, giving an earlier occurrence of $H$. The online construction creates a record for the longest even-palindromic suffix at every step, so it has already made a birth record for $\lambda(Y)$. The empty case uses the distinguished empty record. \end{proof} \begin{intuition} Reflect the proper suffix of the new palindrome across its center. Its mirror copy finishes before the newly appended last letter, so it is wholly old. The online construction has already created a record when that palindrome first appeared. The receipt transports a pointer to that record rather than asking the next transition to rediscover it. \end{intuition} \begin{scope} The theorem says that the required record \emph{exists} in the old history. It does not yet say which old field holds a pointer to it; that is Theorem~\ref{thm:closure}(iv): in the external case it is the receipt stored in the first cell of the live context rope, and in the internal case it is the header of the old rope entry selected by the letter. Nor does the theorem say that the pointer reaches the \emph{birth} record; any record of the right type serves (Section~\ref{sec:map}). \end{scope} The word ``typed'' is essential. A raw endpoint does not identify the needed record at bounded depth. Proposition~\ref{prop:endpoint} makes this precise for the following \emph{endpoint-only} discipline: store, instead of a typed pointer, the time at which the mirror copy of the required palindrome ends, and recover the record by starting from the longest even-palindromic suffix of the prefix ending there and following suffix links downward. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=9mm and 22mm] \node[record] (endpoint) {historical endpoint\\prefix $0^{2m}$}; \node[record, right=of endpoint] (max) {record for\\$0^{2m}$}; \node[record, right=of max] (mid) {$0^{2m-2}$\\$\vdots$\\$0000$}; \node[record, right=of mid] (target) {required record\\$00$}; \draw[flow] (endpoint) -- (max); \draw[flow] (max) -- node[midway, below=3mm, font=\scriptsize]{$m-1$ links} (mid); \draw[flow] (mid) -- (target); \draw[dashedflow, bend right=22] (endpoint.south) to node[below, font=\scriptsize]{typed receipt: one stored pointer} (target.south); \end{tikzpicture} \caption{Endpoint information and typed information are different. The endpoint identifies a historical prefix, but its longest-palindrome record may be arbitrarily high above the required type.} \label{fig:endpoint-receipt} \end{figure} \begin{proposition}[Endpoint-only escape] \label{prop:endpoint} 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,\eps. \] Recovering $00$ from that untyped endpoint takes exactly $m-1$ suffix-link steps. \end{proposition} \begin{proof} The suffix $001100$ is an even palindrome, and no longer suffix of $S_m$ can be a palindrome because any such suffix begins inside the initial zero block but contains its unmatched $11$ asymmetrically. Its longest proper even suffix is $00$. The prefix copy of that $00$ selected by the mirror argument ends at time $2m$. At that time the input is $0^{2m}$, whose longest even suffix is the whole prefix and whose proper even suffixes decrease by two zeros at each link. Starting at $0^{2m}$ reaches $00$ after $m-1$ links. \end{proof} \begin{scope} This is a representation-specific escape theorem, not a language or scaffold lower bound. It says that the positive construction must transport the typed record pointer itself. What generalizes: any discipline that recovers a record by descending a suffix-link chain from an endpoint is unbounded. What is incidental: the particular family $0^{2m}1100$. \end{scope} \section{Why simpler representations fail} \label{sec:representation-failures} The receipt construction was not guessed in its final form. Several natural representations preserve enough extensional information to describe the next palindrome but do not expose the needed immutable pointer within a bounded number of old-field traversals. Recording these failures serves two purposes. It explains why the positive representation carries apparently redundant occurrence data, and it keeps the propositions in their proper scope. None of them is a lower bound for PEGs, scaffolding automata, or palindrome recognition in general. \subsection{Why an immutable type table is not enough} If one record is created at the first birth of each palindrome type, it is tempting to copy a fixed-alphabet transition table from the suffix-link record, as the mutable palindromic tree would do: an entry for letter $a$ pointing to the record of the \emph{target} type $aD_a(P)a$. The target of a later transition, however, need not exist when the source type is born. \begin{proposition}[Future transition after type birth] \label{prop: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 such as $P_r1P_r$. Thus the immutable first-birth record of $P_r$ cannot already point to every future transition out of $P_r$. \end{proposition} \begin{proof} The word $A_r$ is the longest proper even-palindromic suffix of $P_r$ that is immediately preceded by $1$, giving $D_1(P_r)=A_r$. Any occurrence of $T_r=1A_r1$ contains two $1$ symbols separated by $2r$ zeros. In $P_r$ the only adjacent $1$ symbols lie at its center, so no such factor occurs. In $P_r1P_r$, the separator $1$ together with the initial block $A_r1$ of the second copy gives an occurrence of $T_r$. This event is strictly later than the birth record of $P_r$. \end{proof} The forced design decision is modest but decisive: transitions must be transported by occurrence-indexed receipts, or by some representation of equal strength. A canonical type node remains useful for explaining suffix relations, but it is not by itself a closed immutable update interface. The reader may ask why the per-letter entries that the final construction \emph{does} store (Section~\ref{sec:assembly}) escape this proposition. They do because they point to the record of the \emph{selected suffix} $D_a(P)$, which exists when $P$ is born (it is a suffix of $P$), and not to the record of the target $aD_a(P)a$, which may not. \subsection{Why raw persistent words are not enough} A persistent rope can share the letters of a context perfectly. Receipts, however, depend on the palindrome around which those letters are interpreted. \begin{proposition}[Anchor dependence] \label{prop: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. \end{proposition} \begin{proof} The word $0A_r0=0^{2r+2}$ is an even palindrome. Its longest proper even palindromic suffix is $0^{2r}=A_r$. These target types are distinct as $r$ varies. Hence a receipt attached only to the raw letter block cannot be correct for all anchors. \end{proof} This proposition does not forbid structural sharing of the underlying word. It says that the positive object must be an \emph{anchored} receipt path, and that later reuse must justify why the receipt shadow survives a legal change of physical anchor. Lemma~\ref{lem:shadow} supplies exactly that justification. \subsection{Why bounded bridge chasing is not enough} One might defer the missing transition and repeatedly follow the suffix link, testing the bridge letter at each record. The following family makes the number of failed tests arbitrary. \begin{proposition}[Bridge-chasing escape] \label{prop:bridge-chase} 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$ failed bridge tests before reaching the variable target $A_r$. \end{proposition} \begin{proof} The word $P_{r,d}=A_r11A_r11\cdots11A_r$ is unchanged by reversal, so it is an even palindrome. The suffix beginning after the first block $A_r11$ is $P_{r,d-1}$ and is palindromic. No longer proper suffix is palindromic: a suffix beginning inside the first $A_r$ has fewer initial zeros than terminal zeros and meets a $1$ while its reversal is still inside the terminal zero block; a suffix beginning in the following $11$ starts with $1$ and ends with $0$. Hence $P_{r,d-1}$ is the longest proper even-palindromic suffix. The letter immediately before it is the second $1$ of the removed $11$ block. Thus each of the first $d$ records rejects the requested bridge letter $0$ and delegates to its suffix link. At $P_{r,0}=A_r$, the bridge letter before its longest proper even suffix is $0$ (for $r=1$, $\lambda(00)=\eps$ is preceded by the last letter $0$), so the recursion stops. There are exactly $d$ failures, and $d$ is unbounded. \end{proof} The proposition refutes bounded bridge chasing for this representation. It does not refute recursively stored direct transitions: the final construction materializes the same recursion persistently, so the transition selected in a later step is already at bounded depth. \begin{table}[ht] \centering \small \begin{tabularx}{\textwidth}{@{}>{\raggedright\arraybackslash}p{.19\textwidth} >{\raggedright\arraybackslash}p{.21\textwidth} >{\raggedright\arraybackslash}p{.25\textwidth}X@{}} \toprule Attempt & What it preserves & Escape family & Information retained finally \\ \midrule Historical endpoint & where the mirror copy ends & $0^{2m}1100$: target $00$ lies $m-1$ links below the historical maximum & direct typed pointer to the required record \\ Immutable type-birth table & canonical suffix-link type & $P_r=0^{2r}11 0^{2r}$: a needed target is born later & occurrence-indexed transition receipt \\ Anchor-free word rope & persistent raw context letters & the block $0$ over anchors $0^{2r}$ needs different receipts & headered anchored receipt path \\ Bounded bridge chase & correct recursive selector equation & $P_{r,d}$ forces exactly $d$ failures & persistently materialized direct/reset rope \\ \bottomrule \end{tabularx} \caption{Representation lessons. Each escape concerns the interface in the first column, not the expressive power of the target automaton model.} \label{tab:representation-lessons} \end{table} These eliminations narrow the task to a positive one: define an anchored path whose cells carry typed receipts, and prove that the parts shared after an online update retain the same receipt trace even when their concrete palindrome anchors change. That is the purpose of receipt ropes. \section{Receipt ropes and shadow transport} \label{sec:ropes} \begin{question} How can a persistent sequence share an arbitrarily long old tail when the palindrome at the tail's central anchor has changed? \end{question} \subsection{What a receipt rope represents} Consider the current state $(P,\ell)$ with $\ell=c_1c_2\cdots c_k$. If the next input letters happen to be $c_1,c_2,\ldots$ in that order, the external case of Theorem~\ref{thm:context} fires each time: the palindrome becomes $c_1Pc_1$, then $c_2c_1Pc_1c_2$, and so on, while the context loses one letter each time. Each of those future palindromes will need its suffix link at the moment it becomes current (Theorem~\ref{thm:mirror}), and each is determined by $P$ and a prefix of $\ell$. A \emph{receipt rope} stores the context as a sequence of cells, one per context letter, where cell $i$ carries both the letter $c_i$ and the typed receipt for the palindrome obtained after $i$ external matches. Popping a cell (an external match) then exposes, in the next cell, exactly the receipt the new current palindrome needs. The rope is not merely a word with annotations: it is a walk through palindrome occurrences, \emph{anchored} at $P$. The record at the front is a \emph{header}: the receipt of the anchor itself. If a pop makes the first wrapped palindrome current, its suffix-link receipt is promoted to the new header. This promotion is what an ordinary list of letters lacks. \subsection{Definitions} \begin{definition}[anchored path, receipt trace, headered rope] \label{def:rope} For an even palindrome $A$ and a word $w=c_1\cdots c_k$, define the \emph{anchored path} $\Pi(A,w)$ by \[ A_0=A,\qquad A_i=c_iA_{i-1}c_i , \] and write $\wrap_w(A)=A_k$ for its final palindrome. Cell $i$ of the path stores $(c_i,\lambda(A_i))$. Its \emph{receipt trace} is \[ \Lambda(A,w)=(\lambda(A_1),\ldots,\lambda(A_k)), \] and its \emph{headered form} is \[ \widehat\Pi(A,w)= \bigl(\lambda(A);(c_1,\lambda(A_1)),\ldots,(c_k,\lambda(A_k))\bigr), \] whose first component is the \emph{header} and whose sequence of cells is the \emph{body}. Palindrome words in a receipt position denote typed pointers to the particular occurrence records supplied by the construction, not mere type tags. In particular, the displayed header $\lambda(\eps)=\eps$ of a rope anchored at $\eps$ is physically represented by $\emptyrec$. \end{definition} The header is the receipt required if the anchor becomes current; taking a tail promotes the first cell's receipt to the new header. Anchored paths obey the literal catenation law \[ \Pi(A,uv)=\Pi(A,u)\cdot\Pi(\wrap_u(A),v). \] The catenation law carries an important guard: the second path is anchored at the result of wrapping $A$ by $u$. Two identical raw words do not therefore represent interchangeable receipt ropes at arbitrary anchors. Proposition \ref{prop:anchor-dependence} is the one-letter instance of this fact. \begin{example} The live context at row 7 of Table~\ref{tab:running-trace} is $\widehat\Pi(001100,0)=(00;\,(0,00))$: the header is $\lambda(001100)=00$, and the one cell records that after an external match by $0$ the palindrome $00011000$ would have suffix link $00$. \end{example} \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=7mm and 9mm] \node[record] (h1) {header\\$\lambda(A)$}; \node[record, right=of h1] (c1) {$c_1$\\$\lambda(A_1)$}; \node[record, right=of c1] (c2) {$c_2$\\$\lambda(A_2)$}; \node[right=of c2] (dots) {$\cdots$}; \node[record, right=of dots] (tail) {$c_k$\\$\lambda(A_k)$}; \draw[flow] (h1) -- (c1); \draw[flow] (c1) -- (c2); \draw[flow] (c2) -- (dots); \draw[flow] (dots) -- (tail); \node[record, below=13mm of c1] (h2) {promoted header\\$\lambda(A_1)$}; \draw[dashedflow] (c1.south) -- (h2.north); \draw[flow] (h2.east) -| (c2.south); \node[fit=(h1)(c1)(c2)(dots)(tail), draw=black!35, rounded corners, inner sep=4pt, label=above:{\small $\widehat\Pi(A,w)$}] {}; \end{tikzpicture} \caption{A headered receipt rope. Tail removes the first cell and promotes its stored receipt; the persistent remainder is shared. The positive proof must show that legal online reanchoring leaves the receipts in that shared remainder unchanged.} \label{fig:receipt-rope} \end{figure} \subsection{The bridge-shadow identity} The physical palindrome states in a retained context tail can change after a prepend or reset. The next lemma shows that the typed receipt trace does not. Its two anchors $H$ and $P$ are \emph{different words}; the claim is that wrapping them through the same context produces the same sequence of suffix links. \begin{lemma}[Bridge-shadow identity] \label{lem:shadow} Suppose $H=RbP$, $\lambda(H)=P$, and $P$ is the longest even-palindromic suffix of $w^RP$. If $w=\eps$, or if the first letter of $w$ differs from $b$, then \[ \Lambda(H,w)=\Lambda(P,w). \] \end{lemma} (The statement allows $P=\eps$: then $H=Rb$ is any nonempty even palindrome with $\lambda(H)=\eps$, and the hypothesis on $w^RP=w^R$ says $w^R$ has no nonempty even-palindromic suffix.) \begin{example} $H=0000$, $P=\lambda(H)=00$, $b=0$, $w=1$: the hypotheses hold ($1\ne0$; $w^RP=100$ has longest even-palindromic suffix $00$), and indeed $\lambda(1\,0000\,1)=\eps=\lambda(1\,00\,1)$. \end{example} \begin{intuition} The anchors $H$ and $P=\lambda(H)$ begin with the same suffix-link choice as soon as the first context letter is not the bridge $b$. If their receipt traces first diverged later, the unequal bridge exposed at that first divergence could be reflected through the context already consumed. The reflection would form an even-palindromic suffix strictly longer than $P$ in $w^RP$, contradicting the hypothesis that $P$ is longest. The proof below adds indices and a strict length bound to this picture. \end{intuition} \begin{proof} \emph{Strategy.} Compare the two wrapped words cell by cell. Both end in the same suffix; as long as the receipt is strictly shorter than that common suffix, the next bridge letter is read inside it and the two sides agree. The only way the receipt could grow to the full common length is excluded by the maximality hypothesis. For a letter $c$ and even palindrome $X$, put $G_c(X)=\lambda(cXc)$. Every proper even-palindromic suffix of $X$ is a suffix of $\lambda(X)$. Hence \[ G_c(X)= \begin{cases} c\lambda(X)c,&c\text{ is the bridge before }\lambda(X),\\ G_c(\lambda(X)),&\text{otherwise}. \end{cases} \tag{1} \] Write $w=c_1\cdots c_k$, put $u_i=c_1\cdots c_i$, and define \[ X_i=u_i^RHu_i,\qquad Y_i=u_i^RPu_i,\qquad N_i=|P|+i. \] Both $X_i$ and $Y_i$ end in the same word $T_i=Pu_i$, of length $N_i$. We prove for every $i\geq1$ that \[ \lambda(X_i)=\lambda(Y_i)=K_i \quad\hbox{and}\quad |K_i||Y|$ forces $|y|=|Y|+2$, i.e.\ $V=F$, not proper. \end{proof} \begin{corollary} \label{cor:anchor-links} 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$. \end{corollary} \begin{proof} By Lemma~\ref{lem:chunk}, $D_c(Y)$ is defined iff $D_c(L)$ is (for $L=\eps$ both are undefined). Apply Lemma~\ref{lem:mirror-prefix} to $L$ in place of $Y$: the final palindrome of $\Pi(cD_c(L)c,\omega_c(L))$ is $ZcL$, and that of $\Pi(\eps,cL)$ is $LccL$. (For $L=\eps$ the second case reads $\lambda(cc)=\eps$.) \end{proof} \subsection{The receipt-rope recurrence} \begin{theorem}[Receipt-rope recurrence] \label{thm:ropes} 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\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\body\Omega_b(Y). \] \end{theorem} In words, every off-bridge direct rope and every reset rope consists of three pieces already visible at bounded depth: the corresponding rope at the suffix link $L$, one bridge cell, and the body of the single bridge-matching rope at $Y$. The bridge-shadow identity is what makes the third piece literally shareable; without it the equation would describe only equal raw words and would not be a persistent pointer construction. Note that the third piece is shared between two ropes whose anchors differ: in $\Omega_c(Y)$ the cells after the bridge cell are anchored at $b\,(ZcL)\,b$, in $\Omega_b(Y)$ at $bLb$. \begin{proof} \emph{Strategy.} The raw words agree by Lemma~\ref{lem:chunk}; the receipts of the shared tail agree by the bridge-shadow identity applied to all cells but the last, and the last receipts agree by the mirror-prefix lemma. \emph{Raw words.} Let $c\ne b$. By Lemma~\ref{lem:chunk}, $D_c(Y)=D_c(L)$ with the same definedness, and $\omega_c(Y)=\omega_c(L)\,b\,B$. Hence, when defined, $\Omega_c(Y)$ is anchored at the same palindrome $cD_c(L)c$ as $\Omega_c(L)$ and wraps through $\omega_c(L)$, then $b$, then $B$; by the catenation law its first $|\omega_c(L)|$ cells are literally those of $\Omega_c(L)$, its next cell has letter $b$, and its remaining cells are $\Pi(H',B)$ where $H'=b\,\wrap_{\omega_c(L)}(cD_c(L)c)\,b=b(ZcL)b$ with $L=ZcD_c(L)$. In the reset case, $Z_c(Y)=\widehat\Pi(\eps,cLbB)$ similarly begins with the cells of $Z_c(L)=\widehat\Pi(\eps,cL)$, continues with a $b$ cell, and ends with $\Pi(H',B)$ where $H'=b(LccL)b$. On the other side, $\body\Omega_b(Y)=\Pi(bLb,B)$ since $D_b(Y)=L$ and $\omega_b(Y)=B$. \emph{Receipts.} Put $H=ZcL$ (direct case) or $H=LccL$ (reset case), so that $H'=bHb$, and write $B=B'x$ with $x$ its last letter ($B$ is nonempty because $|Y|-|L|-1\ge1$). We claim $\Lambda(H,bB)=\Lambda(L,bB)$; the first entry of this identity is the statement that the $b$ cell of $\Omega_c(Y)$ (resp.\ $Z_c(Y)$) carries $\lambda(bLb)=\rho_b$, and the remaining entries identify $\Pi(H',B)$ with $\Pi(bLb,B)$ receipt by receipt. Apply Lemma~\ref{lem:shadow} with $H$, $P:=L$, and $w:=bB'$. Its hypotheses hold: $H=R'cL$ has bridge $c\ne b$ and $\lambda(H)=L$ by Corollary~\ref{cor:anchor-links}; and $w^RL=B'^RbL$ is $Y$ with its first letter removed, whose even-palindromic suffixes are exactly the proper even-palindromic suffixes of $Y$, the longest being $L$. The lemma gives agreement of the receipts on all cells except the last. For the last cell, the final palindromes are $Yc\,\omega_c(Y)$ (resp.\ $YccY$) on the left and $YbB$ on the right; both have suffix link $Y$ by Lemma~\ref{lem:mirror-prefix}. Hence $\Lambda(H,bB)=\Lambda(L,bB)$, which is the displayed identity. \emph{Definedness.} $\Omega_c(Y)$ is defined iff $\Omega_c(L)$ is, by Lemma~\ref{lem:chunk}; and $Z_c(Y)$ is defined (i.e.\ $D_c(Y)$ undefined) iff $Z_c(L)$ is. \end{proof} \begin{example}[the recurrence on $Y=001100$] Here $L=00$, $b=1$, $B=100$. For $c=0$: $\Omega_0(L)=\widehat\Pi(00,0)=(\eps;(0,00))$, $\Omega_1(Y)=\widehat\Pi(1001,100)=(\eps;(1,11),(0,0110),(0,001100))$, so $\rho_1=\eps$ and the recurrence predicts $\Omega_0(Y)=(\eps;(0,00),(1,\eps),(1,11),(0,0110),(0,001100))$. Direct computation of $\widehat\Pi(00,01100)$ gives the same five cells. The shared tail is anchored at $1\,0000\,1$ on the left and at $1\,00\,1$ on the right; the two anchors differ, and their receipts agree. \end{example} \subsection{Full receipt closure} \begin{theorem}[Full abstract receipt closure] \label{thm: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. \end{theorem} The adjective ``abstract'' marks a clean interface boundary. The theorem has already eliminated suffix-link search, mutation, global interning, and random access to the old input. It assumes only a persistent sequence supporting a fixed collection of operations in worst-case bounded structural work. The next part supplies that sequence and explains how its fresh structural records are represented by the scaffold. Which old \emph{fields} hold the receipts named below is fixed by the record layout of Section~\ref{sec:assembly}. \begin{proof} \emph{Strategy.} Build the fresh record's bridge rope from one old rope by one pop and one inject; build its other entries by Theorem~\ref{thm:ropes}; build the new live context by Theorem~\ref{thm:context}. Suppose the update creates $P=aQa$, where $Q$ is the old longest suffix (external case) or $Q=D_a(P_{\mathrm{old}})$ (internal case), and let $L=\lambda(P)$ as given by Theorem~\ref{thm:mirror}. Select the old rope $\Omega_a(Q)$ when $D_a(Q)$ is defined and the old reset rope $Z_a(Q)$ otherwise; call it the \emph{source rope}. Its body is nonempty (its word is $\omega_a(Q)$, resp.\ $aQ$, and both are nonempty); write the body $(b,H)\mathcal T$. \begin{enumerate}[label=(\roman*)] \item \emph{The bridge of $P$ is $b$.} If $D_a(Q)$ is defined, write $Q=Z'aD_a(Q)$; then $P=aZ'\,aD_a(Q)a=(aZ')L$, so the bridge of $P$ is the last letter of $Z'$, which is the first letter of $\omega_a(Q)=Z'^R$, i.e.\ $b$. If $D_a(Q)$ is undefined, $L=\eps$, the bridge of $P$ is its last letter $a$, and the first letter of the reset rope's word $aQ$ is $a=b$. \item \emph{The header of $\Omega_b(P)$ is $H$.} The header of $\Omega_b(P)=\widehat\Pi(bLb,\omega_b(P))$ is $\lambda(bLb)$. The first cell of the source rope is obtained by wrapping its anchor ($aD_a(Q)a=L$, resp.\ $\eps=L$) by $b$, so its receipt is $H=\lambda(bLb)$. \item \emph{The body of $\Omega_b(P)$ is $\mathcal T$ followed by $(a,P)$.} By (i), $P=(aZ''b)L$ with $Z'=Z''b$, so $\omega_b(P)=Z''^Ra$, while the source rope's word is $\omega_a(Q)=Z'^R=bZ''^R$ (in the reset case $\omega_a(P)=Qa$ and the source word is $aQ$). So $\Omega_b(P)$ wraps $bLb$ through the same letters as the source rope after its first cell, followed by one final letter $a$. By the catenation law the cells coincide with $\mathcal T$, and the final cell has letter $a$ and receipt $\lambda(\wrap_{\omega_b(P)}(bLb))=P$ by Lemma~\ref{lem:mirror-prefix}. In symbols, \[ b_P=b,\qquad \Omega_b(P)=\bigl(H;\mathcal T(a,P)\bigr). \tag{2} \] Operationally: pop the source body, inject the terminal cell $(a,P)$, and reuse the old header $H$. \item \emph{The suffix-link pointer of $P$.} In the external case $Q=P_{\mathrm{old}}$ and $L=\lambda(aP_{\mathrm{old}}a)$ is the receipt stored in the first cell of the live rope $\mathcal K(P_{\mathrm{old}},\ell)$, which the pop of (3) below promotes to the new header. In the internal case $L=\lambda(aD_a(P_{\mathrm{old}})a)$ is the header of the old entry $\Omega_a(P_{\mathrm{old}})$, whose anchor is $aD_a(P_{\mathrm{old}})a=P$. In both cases one old receipt names a record of type $L$. \end{enumerate} Every other entry of the fresh record follows from (2), Theorem~\ref{thm:ropes}, and the finite alphabet: for $c\ne b$, the rope $\Omega_c(P)$ or $Z_c(P)$ is $\Omega_c(L)$ (resp.\ $Z_c(L)$) catenated with the singleton $(b,H)$ and with $\body\Omega_b(P)$---two catenations on ropes read from the record of $L$, which is reached by the pointer of (iv). Let $\mathcal K(P,\ell)=\widehat\Pi(P,\ell)$ be the live context rope. The three cases of Theorem~\ref{thm:context} give \[ \mathcal K'= \begin{cases} \tail\mathcal K(P,\ell),&\ell=a\ell_0,\\ \Omega_a(P)\cdot\body\mathcal K(P,\ell), &D_a(P)\text{ defined},\\ Z_a(P)\cdot\body\mathcal K(P,\ell), &D_a(P)\text{ undefined}, \end{cases} \tag{3} \] where $P$ denotes the old palindrome. The first case is the catenation law read backwards. In the second case the new live rope is $\widehat\Pi(aD_a(P)a,\omega_a(P)\ell)=\Omega_a(P)\cdot\Pi(\wrap_{\omega_a(P)}(aD_a(P)a),\ell)$, and the tail is anchored at $H:=ZaP$ where $P=ZaD_a(P)$; in the third case the tail is anchored at $H:=PaaP$. Lemma~\ref{lem:shadow} applies to $H$, $P$, and $w:=\ell$: $\lambda(H)=P$ by Lemma~\ref{lem:mirror-prefix} (applied to $P$ and $a$), the bridge of $H$ is $a$, the first letter of $\ell$ differs from $a$ in both cases, and $w^RP=\ell^RP=CP=S$, of which $P$ is the longest even-palindromic suffix by definition. So the old body is literally reusable even though its concrete anchor changes. Equations (2)--(3) use a fixed number of rope primitives and old fields. \end{proof} \begin{example}[row 8 at the rope layer] \label{ex:row8-ropes} Before row 8 the state is $P=001100$, $\ell=0$, with live rope $\mathcal K=(00;(0,00))$. The letter is $a=1$, the internal case with $Q=D_1(001100)=00$, and the fresh palindrome is $P'=1001$. The source rope is $Z_1(00)=(\emptyrec;(1,\eps),(0,\eps),(0,00))$ since $D_1(00)$ is undefined; so $b=1$, $H=\eps$, $\mathcal T=((0,\eps),(0,00))$, and (2) gives \[ \Omega_1(1001)=\bigl(\eps;\ (0,\eps),(0,00),(1,1001)\bigr), \] which agrees with the direct definition $\widehat\Pi(11,001)$. The suffix-link pointer of the fresh record is the header of $\Omega_1(001100)=(\eps;(1,11),(0,0110),(0,001100))$, namely $\eps$, the empty record. The new live rope by (3) is \[ \mathcal K'=\Omega_1(001100)\cdot\body\mathcal K =\bigl(\eps;\ (1,11),(0,0110),(0,001100),(0,00)\bigr), \] which is $\widehat\Pi(1001,1000)$ computed directly. The last cell $(0,00)$ was created at row 7 around the anchor $001100$ and is now read around the anchor $1001$; its receipt is unchanged. The terminal cell $(1,1001)$ of the fresh bridge rope points at the fresh record itself: this is the cycle of Part~III. What generalizes: every nonreset update has exactly this shape. What is incidental: the particular lengths. \end{example} \part{Turning bounded records into a scaffold} \section{The cyclic allocation obstacle} \label{sec:cycle} \begin{question} If every rope operation performs only bounded work, why can we not simply allocate its fresh immutable records in topological order? \end{question} \subsection{Records, fields, and batches} From here on a \emph{record} is a finite tuple with a finite \emph{tag}, a finite \emph{payload} (such as a letter), and a fixed number $q$ of \emph{pointer fields}, each of which is missing or points to a record. A persistent program holds a fixed number $s$ of \emph{roots} (pointers kept in finite control) and, at each step, reads old records by following fields from the roots and creates a finite \emph{batch} of fresh records. The fresh batch is a finite labelled directed graph: its vertices are the fresh records (\emph{slots} $0,\ldots,A-1$ for some bound $A$), and each field of each slot is missing, points to an old record, or points to a slot. In ordinary functional programming a fresh record can only point to records that already exist when its constructor runs, so the fresh batch of one step is acyclic and can be allocated in \emph{topological order}: first the records with no fresh targets, then those pointing only to them, and so on. Three small batches show what a cycle would mean. A \emph{self-loop} has one slot $x$ with field $f(x)=x$. A \emph{forward reference} has two slots $x,y$, created in that order, with $f(x)=y$. A \emph{mutual cycle} has $f(x)=y$ and $g(y)=x$. All three are perfectly good finite labelled adjacency tables; none can be produced by allocating one constructor at a time, because the first constructor would have to store a pointer to a record that does not exist yet. \subsection{The cycle the palindrome construction forces} The obstruction is already visible in equation (2) of the closure proof. A fresh palindrome occurrence record $P$ stores the root of its bridge rope $\Omega_b(P)$. The final fresh cell of that rope stores the typed receipt $P$. Thus \[ P\longrightarrow\Omega_b(P) \longrightarrow\text{terminal receipt }P. \] Both edges are semantic requirements of the same input transition. Neither endpoint can be replaced by an old record, and neither ordering of the two fresh objects makes all pointers backward. Example~\ref{ex:row8-ropes} exhibits the cycle concretely: the record for $1001$ and the cell $(1,1001)$ are both created at row 8 and point at each other. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=11mm and 22mm] \node[record] (owner) {fresh occurrence\\owner $P$}; \node[record, right=of owner] (root) {fresh structural root\\of $\Omega_b(P)$}; \node[record, right=of root] (cell) {fresh terminal cell\\$(a,P)$}; \draw[flow] (owner) -- node[above, font=\scriptsize]{rope root} (root); \draw[flow] (root) -- node[above, font=\scriptsize]{structural path} (cell); \draw[flow, bend left=31] (cell.south) to node[below, font=\scriptsize]{typed receipt} (owner.south); \node[fit=(owner)(root)(cell), draw=black!45, rounded corners, inner sep=6pt, label=below:{\small one simultaneous fresh batch}] {}; \end{tikzpicture} \caption{The owner/rope same-step cycle. The steque's structural records are acyclic when the payload $P$ is treated as an opaque atom. Substitution of the fresh owner pointer creates the cycle only at the batch boundary.} \label{fig:owner-cycle} \end{figure} This is not a request for a recursively defined infinite object. After the input letter and bounded old observation are fixed, there are finitely many fresh slots and a finite adjacency table saying which slot each field targets. The graph may contain a cycle, exactly as an ordinary finite directed graph may. Decoding the graph means recovering that adjacency table; it does not mean recursively unfolding the cycle into a tree. A previously considered source interface allowed a fresh field to name only an old object or an earlier fresh slot. That interface silently excludes Figure~\ref{fig:owner-cycle}; proving closure inside it would prove a theorem about the wrong program. The repair is to permit arbitrary references within one uniformly bounded fresh batch and then show that this stronger source step still compiles to the target model. The palindrome batch is larger than the three toy batches but no different in kind. \section{Bounded simultaneous record transducers} \label{sec:compiler} We now define the source machine precisely and compile it into the scaffold model of Definition~\ref{def:scaffolding-automaton}. This section is independent of palindromes: a reader may regard its input as an arbitrary bounded persistent-record update. \subsection{The source model} \begin{definition}[Bounded simultaneous record transducer] \label{def:bsrt} Fix constants $s,A,q,r$. A bounded simultaneous record transducer has $s$ current roots, allocates at most $A$ active slots per input symbol, gives each record $q$ pointer fields, and follows at most $r$ old-record fields from its current roots in one step. Its control states, record tags, and nonpointer payloads are finite. After its bounded old observation, one transition chooses a finite labelled batch graph. Every new root and field targets one of: \[ \missing,\qquad \text{an old address of at most $r$ dereferences},\qquad \text{any active slot of the fresh batch}. \] The last case includes self-loops, forward references, and mutual cycles. The whole finite adjacency table is specified simultaneously. No fresh record is inspected while the plan is chosen, and control does not branch on whether two old addresses name the same record. \end{definition} An \emph{old address} is a root together with a sequence of at most $r$ field names; it is dereferenced by starting at the root and following the named fields. ``Simultaneous'' constrains dependencies rather than prescribing a physical allocation primitive. The plan may depend on finite control and bounded old structure, but it may not branch on a fresh record as though that record had already been evaluated. The adjacency table is output data of the transition. The initial roots may be missing; any fixed finite initial object can be absorbed into finite control and materialized in the first batch. \subsection{Tuple packing} The scaffold appends one node per letter; the transducer creates up to $A$ records per letter. \emph{Tuple packing} resolves the tension: the one physical node $v_t$ appended at time $t$ represents the entire batch born at time $t$, and a finite \emph{slot number} $i{\raggedright\arraybackslash}p{.34\textwidth}X@{}} \toprule slot & record & pointer fields \\ \midrule 0 & occurrence owner $1001$ & suffix link $\to\emptyrec$ (old); bridge $1$; entry $1\to$ slot 1; entry $0\to$ slot 2 \\ 1 & rope value $\Omega_1(1001)$ & header $\eps$ (old receipt $\emptyrec$); body root $\to$ slot 4 \\ 2 & rope value $Z_0(1001)$ & header $\emptyrec$; body root $\to$ slot 5 \\ 3 & live rope $\mathcal K'$ & header $\emptyrec$; body root $\to$ slot 6 \\ 4 & steque node: $\mathcal T$ injected with $(1,\,\cdot)$ & tail $\to$ old cells $(0,\eps),(0,00)$; terminal cell's receipt $\to$ \textbf{slot 0} \\ 5 & steque node: $(0,\eps)\cdot(1,\eps)\cdot\body(\Omega_1(1001))$ & $\to$ old cell, $\to$ fresh singleton, $\to$ slot 4 \\ 6 & steque node: $\body(\Omega_1(001100))\cdot\body(\mathcal K)$ & $\to$ old cells only \\ $\ge7$ & further structural steque records & old or earlier-slot targets \\ \bottomrule \end{tabularx} \end{center} The two roots of the new node point to $(v_8,0)$ and $(v_8,3)$. Every intra-batch pointer is a $\SELF$ port whose tag names the slot; in particular the field of slot 4 that holds the terminal receipt is $\SELF$ tagged $0$, and the entry field of slot 0 is $\SELF$ tagged $1$: that is the cycle of Figure~\ref{fig:owner-cycle}, encoded by two ports of one node. The entry $Z_0(1001)$ is $(\emptyrec;(0,\eps),(1,\eps),(0,\eps),(0,00),(1,1001))$, obtained by Theorem~\ref{thm:ropes} from $Z_0(\eps)=(\emptyrec;(0,\eps))$, the singleton $(1,\rho_1)$ with $\rho_1=\eps$, and $\body\Omega_1(1001)$; the transition receipt of the $0$-entry is absent (reset), that of the $1$-entry is the suffix link $\emptyrec$. What generalizes: the shape of the batch. What is incidental: the slot numbering and the particular steque node structure, which Theorem~\ref{thm:kt} fixes but which the proof never inspects. \end{example} \subsection{Uniform constants} All constructors, letters, table coordinates, and slot tags range over finite sets. The input alphabet is binary and the number of rope operations per step is fixed, so the roots, slots, fields, old observation radius, and fresh allocation bound are constants of one machine. Concretely, let $K$ bound the primitive steps and fresh allocations of any one steque operation of Theorem~\ref{thm:kt} (such a bound exists because each operation is a finite strict decision tree and the elements are opaque). One step performs at most six steque operations (Appendix~\ref{app:inventory}), so it allocates at most $A=6K+4$ slots ($6K$ structural, one owner, two table ropes, one live rope) and reads old records along paths of length at most $r=6K+r_0$, where $r_0$ is the fixed maximum number of non-steque dereferences in the displayed one-step algorithm: root, entry, transition receipt, suffix link, and source- record selectors. Every record constructor has fixed arity; let $q$ be the maximum after padding. Theorem~\ref{thm:compiler} then yields a scaffolding automaton of degree $d=2+Aq$ and distance $r+1$. These are machine constants: $K$ is not an input-dependent estimate but the size of a fixed decision tree, and nothing grows with the prefix length, the current palindrome, the rope length, or the number of historical occurrences. The construction retains an unbounded history, but every next transition observes only this fixed neighbourhood and appends exactly one physical node. \subsection{The run invariant and the theorem} After reading a prefix $S=CP$: \begin{enumerate} \item the decoded occurrence root names a record for the current occurrence of the longest even-palindromic suffix $P$ (the empty record if $P=\eps$); \item the decoded live-rope root denotes $\widehat\Pi(P,C^R)$; \item every table entry in every reachable occurrence record has the word and receipt semantics of Section~\ref{sec:ropes} (its rope is $\Omega_c$ or $Z_c$ of its record's type, and its transition receipt, when present, names a record of type $D_c$ of that type); and \item finite control marks acceptance exactly when the live rope has empty body. \end{enumerate} The empty initial prefix satisfies the invariant using the distinguished empty record and empty rope. One application of the word recurrence chooses the right abstract update; receipt closure proves the new decoded objects have the required semantics; opaque staging and the compiler prove that the single new physical node decodes to those objects. This is the induction performed in the final theorem. \begin{theorem}[Direct palindrome scaffolding] \label{thm:direct} The binary even-palindrome language is recognized by a finite scaffolding automaton: \[ \boxed{\EPAL\in\SA.} \] \end{theorem} \begin{proof} The construction above gives one letter-synchronous finite scaffolding automaton. Its decoded record state follows the exact recurrence by induction on the input length: the invariant holds initially; if it holds before a letter, Theorem~\ref{thm:context} determines the new word state, Theorem~\ref{thm:closure} shows that the fresh record, its entries, and the new live rope computed from old fields have the semantics the invariant requires, Theorem~\ref{thm:staging} shows that this computation is one bounded simultaneous batch, and Theorem~\ref{thm:compiler} shows that the appended node decodes to it. The automaton accepts exactly when the decoded left context is empty, which by Theorem~\ref{thm:context} is exactly $\EPAL$. \end{proof} \begin{corollary}[Direct PEG theorem] \label{cor:peg} \[ \boxed{\EPAL\in\PEG.} \] This proof route uses neither a strict real-time multitape machine nor Slisenko's real-time palindrome theorem. \end{corollary} \begin{proof} Theorem~\ref{thm:lmr} applied to Theorem~\ref{thm:direct} gives $\EPAL^R\in\PEG$. Since the reversal of $ww^R$ is again of the form $uu^R$, the language $\EPAL$ is invariant under reversal, so $\EPAL^R=\EPAL$. \end{proof} \begin{scope} The corollary refutes LMR's Conjecture~7. It does not say anything about palindromes of odd length, about other alphabets (the construction works verbatim over any finite alphabet, with one table entry per letter, but we have not stated it so), or about the class $\SA$ beyond this one language. \end{scope} \part{Result, meaning, and evidence} \section{What the direct route contributes} \label{sec:contribution} The corollary settles no membership question that was still open: the earlier transfer paper \cite{GayStacks2026} already proved $\EPAL\in\PEG$. The contribution is a new factorization of that fact. It exposes the recognition state as a persistent palindrome algorithm and isolates two interfaces that can be reused or challenged independently. First, the palindrome side replaces global mutable type transitions with typed occurrence receipts. The longest-suffix recurrence is represented by headered ropes whose shared tails retain a provably invariant receipt shadow. The endpoint, type-birth, anchor-dependence, and bridge-chasing families explain why each extra coordinate is present. This is a more informative outcome than merely knowing that some real-time machine exists: it identifies the exact historical information a direct immutable recognizer carries. Second, the compiler side shows that a bounded persistent update need not be topologically ordered within one time step. A fixed finite cyclic adjacency table is no harder for a scaffold node to encode than an acyclic one, because all logical fresh records occupy slots of that node and $\SELF$ supplies the common physical target. Opaque-atom staging gives a disciplined way to use this fact with ordinary strict functional data structures: compute their acyclic skeleton first, and tie any semantic payload cycle only in the final simultaneous batch. These results motivate questions about other online algorithms, simultaneous-batch normal forms, and receipt replacements for mutable canonical indexes. Here we prove one compiler theorem and one palindrome application; we do not classify PEGs, scaffolding automata, persistent algorithms, or palindromic data structures. \subsection{Comparison of the two proof routes} The transfer route and the direct route should be viewed as complementary explanations. \begin{center} \small \begin{tabularx}{\textwidth}{@{}p{.21\textwidth}XX@{}} \toprule Coordinate & Earlier transfer route \cite{GayStacks2026} & Direct receipt route (this paper) \\ \midrule Inherited theorem & Slisenko's real-time palindrome recognition \cite{Slisenko1977} (Galil's construction \cite{Galil1978} is a second source) & Kaplan--Tarjan real-time catenable steques \cite{KT1999} \\ Intermediate machine & strict real-time multitape Turing machine & bounded simultaneous persistent records \\ Palindrome state exposed & tape-level state of an external recognizer & longest suffix, occurrence context, typed receipts \\ Scaffold compilation & general machine-to-scaffold transfer & tuple-packed finite fresh batch \\ Final statement & $\EPAL\in\PEG$ & $\EPAL\in\PEG$ \\ \bottomrule \end{tabularx} \end{center} Agreement at the final statement is useful assurance, but the routes are not independent proofs of every intermediate lemma: both eventually use the Loff--Moreira--Reis scaffold-to-PEG direction. Their internal palindrome arguments and scaffold source models are different. A defect in the direct receipt construction would not retract the earlier membership result; it would invalidate the claimed persistent explanation and compiler application. \subsection{Why the negative representation results matter} The four escape families are small mathematical results with deliberately narrow conclusions. Their value is diagnostic. Each converts an intuitive but underspecified implementation proposal into an exact doctrine and then exhibits an unbounded parameter that doctrine fails to expose. The residue of the failure becomes the next positive invariant: endpoint escape motivates typed pointers; future type transitions motivate occurrence receipts; anchor dependence motivates anchored ropes; bridge escape motivates recursively materialized direct ropes and their transition receipts. The final coordinate system is not asserted to be canonical. It is the first one in this chain for which every semantic update, persistent operation, and scaffold address closes with an explicit uniform bound. \section{Assurance, provenance, and the viewpoint} \label{sec:assurance} \subsection{What kind of evidence supports what} The theorems of this paper have ordinary written mathematical proofs. The public package also contains executable checks; they answer different questions, and none of them changes the mathematical status of a theorem. \begin{center} \begin{tabularx}{0.94\textwidth}{>{\bfseries}l X} \toprule Layer & What it establishes\\ \midrule Written proof & the stated theorem for all objects satisfying its hypotheses\\ Finite audit & exact behavior over one explicitly bounded search domain\\ Source audit & the external theorem or model says what the paper attributes to it\\ Specialist review & an independent reader has attacked correctness and positioning\\ Novelty review & the contribution has been compared broadly enough to support priority language\\ \bottomrule \end{tabularx} \end{center} The public package contains five independent Python programs. They check the three-case context recurrence, typed mirror receipts, receipt-rope closure, simultaneous cyclic batch decoding, and the modern catenable-interface calibration, on exhaustive domains of words up to a fixed length and on random longer instances (counts are recorded in the package's \texttt{audit/RUN-OUTPUT.txt}). The programs use exact finite words and pointer graphs. They corroborate the displayed identities and protect against regression, but bounded computation is not the proof of a universal theorem. The checks are intentionally divided at the same seams as the proof: a word checker has no implementation of scaffolds; the compiler checker generates bounded record heaps and cyclic batches without palindrome semantics; the source-interface checker inspects a pinned catenable implementation without assuming the receipt equations. This separation is not complete logical independence, but it reduces the chance that one shared encoding mistake makes every check agree. Three boundaries should remain visible. \begin{enumerate} \item The conclusion $\EPAL\in\PEG$ was already proved by the earlier real-time transfer route \cite{GayStacks2026}. This paper contributes a direct persistent record route. \item Endpoint-only, type-birth-only, and bounded bridge-chasing failures are representation-specific. They are not lower bounds against all scaffolding automata. \item External specialist review and a broader novelty search remain open. A complete written proof is not the same coordinate as novelty or review status, and no novelty claim is made here. \end{enumerate} \subsection{Provenance and AI assistance} The arguments were developed in FPRD Lab, an AI-assisted research project. The mathematics is the author's responsibility; AI systems drafted and checked text and code under the author's direction, and an adversarial pass by such a system found, before publication, that an earlier version of the source model excluded the very cycle its own receipt equation creates (Section~\ref{sec:cycle}); the present simultaneous model is the repair. The primary sources \cite{LMR2020,KT1999} were read in full and the exact statements used are quoted with page numbers; copies and extracted text are held locally and are not part of the public repository. No proof assistant is used for this paper; an existing Lean development of the project independently reconstructs LMR's sufficient direction, but the paper cites the published theorem and does not rely on that reconstruction. \subsection{The viewpoint, stated more fully} The viewpoint of Section~\ref{sec:map} can be stated as a discipline with four layers, each implication between which is a theorem obligation: \begin{enumerate} \item \emph{Semantic algebra}: exact recognition behaviors and their constructors, quotiented only by exact behavior equality. \item \emph{Observational completion}: finite interfaces---for example, agreement on all inputs through a bounded length---and their quotient maps. \item \emph{Presentation-generated dynamics}: a distinguished initial state and named actions extracted from, or supplied by, one finite presentation. \item \emph{Coordinate realization}: an injective state encoding, coordinates for every named action, and a uniform readout recovering recognition behavior from coordinates and input. \end{enumerate} In this paper the exact word recurrence and receipt equations supply the semantic behavior; bounded old-record and scaffold unfoldings are the finite interfaces; input letters generate the persistent occurrence dynamic; and the tuple-packed compiler supplies both an injective scaffold encoding and its uniform decoder. Acceptance is the final observation that the reversed context is empty. The transfer route of \cite{GayStacks2026} studies a different presentation-generated dynamic with the same language observation; the two routes therefore complement one another even though both end at $\EPAL\in\PEG$. Changing the observation may merge states without changing the presentation; changing the presentation may change internal actions without changing the accepted language. Both phenomena are kept visible rather than quotiented away at the start. This failure-to-invariant progression (Section~\ref{sec:representation-failures}) is where the viewpoint affected the proof most visibly: instead of treating a convenient representation as the recognition dynamic, the investigation repeatedly projected the same word semantics into competing persistent coordinates and asked which observations remain bounded. \appendix \section{Notation} \label{app:notation} Table~\ref{tab:notation} collects the symbols whose meanings cross more than one proof layer. A symbol naming a word is not silently identified with the record that represents an occurrence of that word. \begin{table}[ht] \centering \small \begin{tabularx}{\textwidth}{@{}p{.18\textwidth}X@{}} \toprule Symbol & Meaning \\ \midrule $S=CP$ & input prefix, factored at its longest even-palindromic suffix $P$ \\ $\ell=C^R$ & reversed occurrence context; its head is immediately left of $P$ \\ $\lambda(P)$ & suffix-link word: longest proper even-palindromic suffix of nonempty $P$; $\lambda(\eps)=\eps$ by convention \\ $b_P$, $B_P$ & bridge letter and bridge block: $P=\lambda(P)\,b_P\,B_P$ \\ $D_a(P)$ & longest proper even suffix of $P$ immediately preceded by $a$ \\ $\omega_a(P)$ & reversed word displaced into context when $D_a(P)$ is wrapped \\ $\Pi(A,w)$, $\wrap_w(A)$ & anchored palindrome path obtained by wrapping $A$ through $w$, and its final palindrome \\ $\Lambda(A,w)$, $\widehat\Pi(A,w)$ & its receipt trace; its headered rope \\ $\Omega_a(P)$ & direct receipt rope when $D_a(P)$ exists \\ $Z_a(P)$ & reset receipt rope when $D_a(P)$ does not exist \\ $\mathcal K(P,\ell)$ & the live context rope $\widehat\Pi(P,\ell)$ \\ $\emptyrec$ & the distinguished record representing a typed receipt to the empty palindrome \\ $\SELF$, $\missing$ & scaffold descriptors: the node being appended; no edge \\ $(v,i)$ & decoded logical record: physical node $v$ and finite slot $i$ \\ $s,A,q,r$ & roots, slots per step, fields per record, old dereference radius \\ \bottomrule \end{tabularx} \caption{Notation crossing the word, record, and scaffold layers.} \label{tab:notation} \end{table} \section{Fixed allocation inventory} \label{app:inventory} The proof needs uniform finiteness, not optimized constants. Nevertheless an explicit inventory prevents the phrase ``constant number of operations'' from hiding an input-dependent loop. Let $K$ simultaneously bound the primitive observations and fresh structural constructors performed by any one Kaplan--Tarjan operation used by the algorithm. Such a maximum exists because the relevant operations have a finite strict decision tree and the element payloads are opaque. In the worst binary branch, the receipt update invokes at most six sequence operations: \begin{enumerate} \item one pop to expose the body of the source direct or reset rope; \item one inject to add the terminal receipt carrying the fresh owner; \item one singleton construction for the new bridge cell; \item two catenations for the off-bridge direct or reset table entry; and \item one pop or catenation for the new live context. \end{enumerate} Charging $K$ fresh structural slots to each call gives $6K$ slots. Four additional logical values suffice at the receipt layer: the fresh occurrence owner, two table-rope values, and the live-rope value. Thus $A=6K+4$ is a conservative simultaneous allocation bound. Old observation is bounded similarly. The non-steque dereferences of one step are: root to current record; its $a$-entry; the entry's transition receipt (internal case); the source record's $a$-entry and rope; the suffix-link pointer obtained by Theorem~\ref{thm:closure}(iv); and the $c$-entry of the suffix-link record---at most eight. Inlining at most six operation trees gives the conservative radius $r=6K+8$. With $s=2$ roots and $A$ slots, Theorem~\ref{thm:compiler} yields physical degree $d=2+Aq$ and distance $r+1$. Sharing may make the actual numbers smaller, and an optimized layout may combine some values, but no such optimization is used by the proof. These are machine constants; they do not grow with the prefix length, the current palindrome, the receipt-rope length, or the number of historical occurrences. \section{Claim and reproducibility map} \label{app:reproducibility} The publication package separates mathematical statements from the mechanisms used to challenge them, and records each theorem under an identifier in the project's claim ledger. FPRD-D36 is Definition~\ref{def:bsrt}. FPRD-T125 is the receipt package comprising Theorems~\ref{thm:context}, \ref{thm:mirror}, \ref{thm:ropes}, and \ref{thm:closure}, with Lemmas~\ref{lem:shadow} and \ref{lem:mirror-prefix}. FPRD-T126 is Theorem~\ref{thm:compiler}. FPRD-T127 is Theorem~\ref{thm:staging}. FPRD-T128 is Theorem~\ref{thm:direct} and Corollary~\ref{cor:peg}. These identifiers are bookkeeping; they carry no mathematical weight. The five public checkers correspond respectively to occurrence-context words, mirror receipts, receipt closure and shadow reuse, simultaneous record compilation, and the catenable-sequence interface. Their canonical output is stored with the paper so that a rerun can be compared byte for byte. The package verifier rebuilds the PDF, checks its reader-facing anchors and size guardrails, reruns the focused mathematical audits, and checks the central claim/publication registries. Primary papers and external source checkouts are intentionally not copied into the public repository. The source audit records titles, versions, links, local checksums, and exactly which theorem or source property is used. A successful checker run is evidence about the tested finite instances or pinned source; it does not change the mathematical status of a theorem, certify novelty, or substitute for specialist review. \section{Modern source calibration} \label{app:source-calibration} Viennot, Wendling, Gu\'eneau, and Pottier give a later OCaml implementation and a separate Rocq implementation of Kaplan--Tarjan catenable deques \cite{VWGP2025}. Their paper clearly separates the evidence: the OCaml code is tested but not verified; the Rocq code has machine-checked functional correctness; there is no formal correspondence between the two; and the Rocq extraction does not establish the same constant-time bound because runtime indices are retained. We therefore use Kaplan--Tarjan's Theorem~\ref{thm:kt} as the mathematical premise. The modern source is a hostile implementation calibration. At the pinned commit recorded in the package's source audit, its operational core is strict and nonrecursive, but the audit found two exact mismatches with an opaque finite-record interface: four classifiers read an exact unbounded buffer length, and the noncatenable empty test uses OCaml polymorphic structural equality. The first is extensionally replaced by fixed persistent end probes; no classifier uses more than twelve primitive root observations. The second is replaced by matching the outer empty constructor. On valid inputs the original equality already stops at that constructor, before any element is inspected, but the replacement makes opacity explicit. These repairs are checked through length 512. This evidence is not described as verification of the OCaml program and is not needed for Theorem~\ref{thm:direct}. This separation matters because ``functionally verified'' and ``satisfies the bounded-record cost interface'' are different coordinates. Neither coordinate alone is silently promoted into the conjunction needed here. The mathematical proof instead uses the original Kaplan--Tarjan theorem and the staging lemma. \section*{Acknowledgment of inherited work} Kaplan--Tarjan catenable steques and the Loff--Moreira--Reis scaffold/PEG correspondence are inherited mathematical results. The Viennot et al.\ implementations are external work used for calibration. This paper contributes the occurrence-context formulation, typed receipt system, representation escape audits, simultaneous cyclic source model, tuple-packed compiler, opaque-atom staging bridge, direct composition, and the adversarial correction that exposed the same-step cycle before publication. Detailed attribution is recorded in the accompanying package files. \begin{thebibliography}{99} \bibitem{ChomskySchutzenberger1963} Noam Chomsky and Marcel-Paul Sch\"utzenberger. \newblock The algebraic theory of context-free languages. \newblock In P.~Braffort and D.~Hirschberg, editors, \emph{Computer Programming and Formal Systems}, Studies in Logic and the Foundations of Mathematics, pages 118--161. North-Holland, Amsterdam, 1963. \bibitem{DSST1989} James R. Driscoll, Neil Sarnak, Daniel D. Sleator, and Robert E. Tarjan. \newblock Making data structures persistent. \newblock \emph{Journal of Computer and System Sciences}, 38(1):86--124, 1989. \newblock \url{https://doi.org/10.1016/0022-0000(89)90034-2}. \bibitem{Ford2004} Bryan Ford. \newblock Parsing expression grammars: A recognition-based syntactic foundation. \newblock In \emph{Proceedings of POPL 2004}, pages 111--122. ACM, 2004. \newblock \url{https://doi.org/10.1145/964001.964011}. \bibitem{Galil1978} Zvi Galil. \newblock Palindrome recognition in real time by a multitape Turing machine. \newblock \emph{Journal of Computer and System Sciences}, 16(2):140--157, 1978. \newblock \url{https://doi.org/10.1016/0022-0000(78)90042-9}. \bibitem{GayStacks2026} Joshua Gay. \newblock Real-time multitape languages transfer to parsing expression grammars. \newblock FPRD Lab review paper, released 5 August 2026. \newblock \url{https://gitlab.com/insight-forge/boxlab/fprd-lab/-/tree/main/publications/persistent-stacks-scaffolding}. \bibitem{KT1999} Haim Kaplan and Robert E. Tarjan. \newblock Purely functional, real-time deques with catenation. \newblock \emph{Journal of the ACM}, 46(5):577--603, 1999. \newblock \url{https://doi.org/10.1145/324133.324139}. \bibitem{LMR2020} Bruno Loff, Nelma Moreira, and Rog\'erio Reis. \newblock The computational power of parsing expression grammars. \newblock \emph{Journal of Computer and System Sciences}, 111:1--21, 2020. \newblock \url{https://doi.org/10.1016/j.jcss.2020.01.001}. \newblock Expanded preprint arXiv:1902.08272v2 (2020); definition and theorem numbers in this paper follow the preprint. \bibitem{RubinchikShur2018} Mikhail Rubinchik and Arseny M. Shur. \newblock EERTREE: An efficient data structure for processing palindromes in strings. \newblock \emph{European Journal of Combinatorics}, 68:249--265, 2018. \newblock \url{https://doi.org/10.1016/j.ejc.2017.07.021}. \newblock Preprint arXiv:1506.04862. \bibitem{Slisenko1977} A.~O. Slisenko. \newblock A simplified proof of the real-time recognizability of palindromes on Turing machines. \newblock \emph{Zapiski Nauchnykh Seminarov LOMI}, 68:123--139, 1977. \newblock English translation in \emph{Journal of Soviet Mathematics}, 15:68--77, 1981, \url{https://doi.org/10.1007/BF01404109}. \bibitem{VWGP2025} Jules Viennot, Arthur Wendling, Arma\"el Gu\'eneau, and Fran\c{c}ois Pottier. \newblock Verified purely functional catenable real-time deques. \newblock arXiv:2505.07681v3, 3 July 2026. \newblock \url{https://arxiv.org/abs/2505.07681v3}. \end{thebibliography} \end{document}