\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]{FPRD Lab review paper} \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} \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}} \newcommand{\EPAL}{\mathsf{EPAL}_2} \newcommand{\SA}{\mathsf{SA}} \newcommand{\PEG}{\mathsf{PEG}} \newcommand{\eps}{\epsilon} \newcommand{\missing}{\varnothing} \newcommand{\SELF}{\mathsf{SELF}} \newcommand{\tail}{\operatorname{tail}} \newcommand{\body}{\operatorname{body}} \newcommand{\wrap}{\operatorname{wrap}} \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}, 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{21 August 2026} \begin{document} \maketitle \begin{abstract} Loff, Moreira, and Reis conjectured that the language $\EPAL=\{ww^R:w\in\{0,1\}^*\}$ has no parsing expression grammar. That conjecture has already been refuted by an FPRD Lab transfer through strict real-time multitape machines. Here we give an independent direct route and make explicit the persistent memory discipline executed by the scaffold. The recognizer maintains the longest even-palindromic suffix and the reversed context of its current occurrence. Typed receipts name historical suffix-link occurrences directly; persistent receipt ropes update that context by a bounded number of sequence operations. The construction then encounters a genuine same-step cycle: a fresh palindrome owns a fresh rope whose terminal receipt points back to that palindrome. To express this without smuggling in mutation, we define bounded simultaneous record transducers. Their fixed finite fresh-batch graphs compile into single scaffold nodes using $\SELF$ together with finite slot tags. Kaplan--Tarjan real-time catenable steques supply the sequence operations, and an opaque-atom staging theorem shows why their acyclic structural allocation can be tied to the fresh owner only at the simultaneous encoding boundary. The resulting finite scaffolding automaton recognizes $\EPAL$, and the Loff--Moreira--Reis correspondence yields $\EPAL\in\PEG$ without a Turing machine or Slisenko's palindrome theorem. The paper is written for formal-language, automata, parsing, and adjacent mathematics researchers; it separates the word recurrence, persistent representation, physical scaffold, and executable checks. The package is released for specialist review. The membership result is not first, and no novelty claim is made pending broader literature review. \end{abstract} \tableofcontents \part{Why this proof looks different} \section{The question and the direct route} \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} A parsing expression grammar (PEG) is a deterministic recognition formalism whose ordered choice and predicates differ fundamentally from the usual nondeterministic reading of a context-free grammar. Loff, Moreira, and Reis introduced scaffolding automata and proved that a language is recognized by a PEG exactly when its reversal is recognized by a finite scaffolding automaton \cite{LMR2020}. They conjectured that \[ \EPAL=\{ww^R:w\in\{0,1\}^*\} \] does not belong to $\PEG$. For a reader coming from automata theory, there are two useful cautions. A PEG is not a context-free grammar equipped with a preferred parsing algorithm: ordered choice is semantic, and failure may be used by predicates. Conversely, the theorem used here does not require us to synthesize a readable grammar rule by rule. It is enough to construct a finite scaffolding automaton. That automaton reads from left to right, appends one persistent node at each step, and bases its next transition on a fixed-radius view of the current top. The Loff--Moreira--Reis theorem then converts this finite recognition process into a PEG for the reversed language. FPRD Lab has already refuted that conjecture by compiling strict real-time multitape machines into scaffolding automata and using a classical real-time palindrome theorem. The result here is not a first refutation. Its purpose is to remove the Turing-machine detour and identify the persistent data structure that the scaffold itself executes. \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) {strict real-time\\multitape recognizer}; \node[box, right=of rt] (transfer) {general RT-MTTM\\to scaffold transfer}; \node[box, right=of pal, yshift=-9mm] (receipts) {occurrence receipts\\and persistent ropes}; \node[box, right=of receipts] (direct) {bounded simultaneous\\record compiler}; \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} (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. Its point is the direct persistent representation, not a new first refutation.} \label{fig:two-routes} \end{figure} The lower route in Figure~\ref{fig:two-routes} produces two mathematically separable results. The application is a direct finite scaffold for even palindromes. The reusable intermediate result is a compiler: any transition which observes only bounded old structure and specifies a bounded finite graph of fresh records---even a graph with cycles among those fresh records---can be encoded by one scaffold node. The palindrome proof forces precisely the cycle that makes this strengthening necessary. \subsection{The general aim: presentations, dynamics, and observations} This paper builds directly on the framework introduced by Loff, Moreira, and Reis in \emph{The Computational Power of Parsing Expression Grammars} \cite{LMR2020}. 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 whether $\EPAL$ has some PEG. It is which finitely presented recognition dynamic makes palindrome comparison visible to that correspondence. That question is representative of what we call \emph{finitely presented representation dynamics} (FPRD). The basic factorization is \[ \text{finite recognition presentation} \longrightarrow \text{recognition dynamics} \longrightarrow \text{language or suffix observation}. \] FPRD first asks what exact state space, named actions, topology, finite observations, and boundary behavior a finite presentation generates. It then asks which part of that richer object a chosen observation exposes. 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. The deterministic foundation separates four layers. \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---their quotient maps, and compatible inverse threads. \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} An implication between layers is a theorem obligation. A universal product embedding is not automatically a useful coordinate realization; a state encoding without a uniform readout is incomplete; language equality does not imply equality of labelled continuation actions. Conversely, two models may share a coordinate topology and action monoid while exposing different remaining-suffix observations. 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 companion RT-MTTM route 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$. \begin{quote} \textbf{Main application (FPRD-T128; proved in Section~\ref{sec:assembly}).} There is a finite scaffolding automaton recognizing the binary even-palindrome language. Consequently $\EPAL\in\PEG$. This construction uses neither a strict real-time multitape machine nor Slisenko's real-time palindrome theorem. \end{quote} Stating the result now gives the reader a fixed target: all intervening definitions exist to explain what information the single new scaffold node must contain and how that information is obtained locally. \subsection{Assurance boundary} The proof has four layers. \begin{enumerate} \item The longest even suffix and its reversed left context obey an exact three-case recurrence. \item Typed mirror receipts and bridge-shadow identities turn that recurrence into a fixed collection of persistent rope operations. \item Kaplan and Tarjan's purely functional real-time catenable steque \cite{KT1999} supplies those rope operations with worst-case bounded structural work. \item A bounded simultaneous record transducer compiles letter-for-letter into one finite scaffolding automaton. \end{enumerate} The written arguments are mathematical proofs. The accompanying programs are finite corroborations and regressions, not proofs of the infinite statements. The later OCaml/Rocq implementations of Viennot et al. \cite{VWGP2025} are used as implementation calibration, not as the functional-correctness premise. No Lean reconstruction of this paper is claimed or required. External specialist review and novelty evaluation remain open. \section{A reader's map} The argument moves through three representations of the same online state. Keeping them separate prevents most of the apparent paradoxes. \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 may attach 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. \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); \draw[flow] (batch) -- (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} We assume ordinary familiarity with words, palindromes, finite-state control, persistent immutable records, and inductive proofs of simulation. We do not assume prior familiarity with scaffolding automata, PEG semantics, palindromic trees, catenable steques, or the FPRD research program. Definitions are given at the first point where they carry proof weight. 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, 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 checked 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 nonempty even suffix can be wrapped, so the new longest even suffix is empty. \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 and gives concrete names to the otherwise abstract objects. \part{Persistent palindrome state} \section{The occurrence-context 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: 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. 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$. For an even palindrome $P$ and a letter $a$, let $D_a(P)$ be the longest proper even-palindromic suffix $Q$ for which \[ P=ZaQ, \] and put $\omega_a(P)=Z^R$. Both are undefined when no such factorization exists. 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{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,\tail(\ell)), &\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} 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. This interpretation 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. The chunks $\omega_a(P)$ themselves satisfy a finite-alphabet recursion. If $L=\lambda(P)$ is the longest proper even-palindromic suffix and \[ P=RbL=LbR^R, \] write $B_P=R^R$. Then \[ D_b(P)=L,\quad \omega_b(P)=B_P, \] and for $a\ne b$, \[ D_a(P)=D_a(L),\qquad \omega_a(P)=\omega_a(L)bB_P, \] with the same definedness on both sides. Indeed, every proper even-palindromic suffix of $P$ is a suffix of $L$; the bridge letter $b$ selects $L$ itself, while every other letter delegates to $L$ and adds the displayed intervening block. 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} 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 normally inexpensive in an online palindromic tree: a mutable 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 the exact palindrome record 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 palindrome $H$, it is the longest palindromic suffix of the prefix ending there. Otherwise a longer palindromic suffix would contain $H$ as a proper prefix as well as a suffix, giving an earlier occurrence of $H$. The online construction has therefore already made a birth record for $\lambda(Y)$. The empty case uses one 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} The word ``typed'' is essential. A raw endpoint does not identify the needed record at bounded depth. \begin{figure}[ht] \centering \begin{tikzpicture}[node distance=9mm and 15mm] \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[above, font=\scriptsize]{$m-1$ suffix links} (mid); \draw[flow] (mid) -- (target); \draw[dashedflow, bend right=25] (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} 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. \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 a mutable palindromic tree would do. 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. \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$, 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} \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} A receipt rope is not merely a word rope with annotations. It represents a walk through palindrome occurrences. Starting from an anchor $A$, each context letter wraps the current palindrome and each cell records the suffix link of the newly wrapped palindrome. The record at the front is a \emph{header}: if a tail operation makes the first wrapped palindrome current, its suffix-link receipt is already exposed. This promotion is what an ordinary list of letters lacks. For an even palindrome $A$ and word $w=c_1\cdots c_k$, define the anchored path $\Pi(A,w)$ by \[ A_0=A,\qquad A_i=c_iA_{i-1}c_i. \] Cell $i$ stores $(c_i,\lambda(A_i))$. Its receipt trace is \[ \Lambda(A,w)=(\lambda(A_1),\ldots,\lambda(A_k)), \] and its headered form is \[ \widehat\Pi(A,w)= \bigl(\lambda(A);(c_1,\lambda(A_1)),\ldots,(c_k,\lambda(A_k))\bigr). \] 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{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} 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. \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} \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} 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|