The Setting
In the local-rule machinery underlying the group construction, configurations are represented as finite words of cells organized into blocks, where active reading heads and palette color checkers carry out bounded local computations. Elementary rewriting rules modify only one or two adjacent cells at a time, while arbitrary surrounding subwords flank the modified region.
First, do admissible single-cell and two-cell replacements preserve global word syntax in arbitrary surrounding contexts and across multi-step derivations? Second, in a sequence of cells with compatible adjacent skeletons, does every non-idle cell belong to a region with a unique active head, and under a rigid block layout does that region encompass every core cell of its blocks?
Positions, Skeletons, and Palette Checkers
Let be a bound parameter. A block cell position in is either a core position with , a palette position with color index , or the stop position .✦ A cell shape in is either with , , or .✦ A cell marker is one of five tags: , (left wing), , (full active head), or (right wing).✦
For an arity bound , a block metadata record in is a triple consisting of an arity , a Boolean zero-task flag , and a block index .✦ Taking gives the cell arity metadata set ✦, with default metadata .✦
A cell syntactic skeleton is a triple consisting of a position , a marker , and metadata .✦ Given a marker , the marked skeleton replaces by while preserving and .✦ A skeleton carries an active head marker if .✦ An initial skeleton is a skeleton with and , and a terminal skeleton is a skeleton with and . An admissible skeleton is a skeleton such that whenever is initial and whenever is terminal.✦
A left-external skeleton is a skeleton such that , or and is initial.✦ A right-external skeleton is a skeleton such that , or and is terminal.
Two skeletons are structurally adjacent if their positions satisfy one of five rules: and with ; and with ; both and are palette positions; is a palette position and ; or and with .✦ A skeleton accepts a marker on the left if when , and otherwise; accepts on the right if when , and otherwise.✦ A pair of skeletons satisfies internal skeleton consistency if , , when and otherwise, is not initial, and is not terminal.✦
A compatible adjacent skeleton pair is a pair of structurally adjacent skeletons such that either is right-external and is left-external, or neither is external, accepts on the right, accepts on the left, and satisfies internal skeleton consistency.✦ Extending with a blank boundary symbol , the skeleton link relation holds on , on when is left-external, on when is right-external, and on when is a compatible adjacent skeleton pair.✦ A finite sequence of skeletons in is closed if every is admissible and every adjacent pair in satisfies the link relation.✦
For a color set , a palette checker state in is , with a sought color , or an active checker head seeking .✦ Two adjacent checker states in form a compatible checker pair if both are , both are for the same , the left is and the right is for the same , or the left is and the right is .✦ A checker state satisfies the terminal checker condition if it is or for some , and fails if it is .✦
Cells, Tasks, and Word Syntax
A three-bit register state is a map on .✦ A head computation phase is one of nine stages: , , , , , , , , or .✦ An endpoint phase is a phase that is , , , , or .✦ A reading head state is a quadruple consisting of a side , a clause index , a head computation phase , and a register state ; the default head state is .✦
For a bound , a finite table cell consists of a skeleton , a checker state , a pair of data bits , a certificate bit , and a reading head state .✦ For a cell , its position , marker , and metadata are those of , and its cell shape maps to , any to , and to .✦ A cell is in the core if for some ✦, and is in the palette if for some .✦ A head-free cell is a cell whose skeleton does not carry an active head marker and whose checker satisfies for every .✦
A cell memory address is either a data address specified by a side , a block index , and a position , or a certificate address specified by .✦ Reading a cell at an address yields a bit : when with , it returns if and , and returns if and ; otherwise it returns .✦
A verification task specification is a pair consisting of an arity and a zero-task flag .✦ The task projection sends metadata to , and for a cell we write .✦ A verification clause of bound consists of three addresses and a Boolean truth function .✦ Given a clause and a cell , the clause register delta has entries for .✦ A verification clause schedule of bound assigns to each task a positive clause count and to each with a verification clause .✦
Given a schedule of bound and a data size , a cell satisfies the cell formatting condition for and when its head satisfies (1): (1)✦ Two adjacent cells satisfy checker compatibility if whenever both are in the palette is a compatible checker pair, and whenever is in the palette and , satisfies the terminal checker condition.✦ Given a schedule of bound and a data size , a finite cell word of cells in satisfies the cell word syntax condition when (2) holds: (2)✦
Local Replacements and Reachability
Given a cell and a side , the idle cell keeps and , resets the marker to , metadata to , head to , and certificate to , and sets its data function to and .✦ Given a cell and a side , the boundary cell sets the skeleton of to and the head to .✦ Given a cell and a marker , the wing cell sets the skeleton of to and the head to ; for a side , clause index , phase , and register state , the full cell sets the skeleton to and the head to . Given a cell , checker state , and color , the checker update replaces by ✦, and the color update replaces the position in by .✦
For a schedule of bound , the unary cell transition on holds across the twelve rules in (3), where , , , and : (3)✦
For cells , write when is a compatible adjacent skeleton pair, and when is a compatible adjacent skeleton pair. For , write . The binary cell transition holds across the eight adjacent-cell rules in (4), where , , , and : (4)✦
Given a schedule of bound and a data size , two cell words satisfy the replacement relation if every cell appearing in or satisfies cell formatting for and , and either and with or , or and with or .✦ A cell word rewriting step holds if there exist cell words such that , , and .✦ Cell word reachability is the reflexive-transitive closure of .✦
Regions, Ownership, and Rigid Block Layouts
A finite sequence of length is coherent if and form a compatible adjacent skeleton pair for all with .✦ The exterior boundary condition holds for a sequence of length if is left-external whenever and right-external whenever .✦
Given a cut predicate on , two indices are connected without cuts if for every satisfying .✦ For , the cell cut predicate holds when is right-external.✦ Two indices lie in the same region of a sequence , written , if and are connected without cuts with respect to .✦ An index owns an index in , written , if and carries an active head marker.✦ For each , the region component is the set ✦, and its left endpoint is .✦
For a bound , the rigid block width is .✦ Each coordinate has block coordinate position given by for , for , and for , and block coordinate shape given by for , for , and for . For blocks of width , an index has block index in and block coordinate in . Conversely, a block and offset yield the cell index ✦, and for the core index is .✦
A sequence has a rigid block layout if for all .✦ Given a sequence in rigid block layout and an index satisfying the local skeleton and cell hypotheses for region blocks, each offset defines a region block index .✦
The Claim
Theorem 1. Let be a verification clause schedule of bound and let be a data size. For any cell words satisfying and any cell words , (5)✦ For any cell words with such that holds, (6)✦
Let be a coherent cell sequence satisfying the exterior boundary condition. For every index with , (7)✦ If is coherent and satisfy with both and carrying active head markers, then (8)✦
Let be a sequence in rigid block layout such that the cell word satisfies the cell word syntax condition , and let be an index with . For every and every core position , (9)✦
In the paper, the result reads: starting from a concatenation of complete clean blocks, the structural, transaction, and checker syntax () is preserved under all elementary replacements, distinct transactions never own cells of the same block, and the elementary moves are context safe at both untouched neighboring letters, even when two transaction regions abut. The library states these properties in terms of prefix-suffix word concatenation and reachability in (5) and (6), and cut-connected regions in rigid block layouts in (7) through (9).
What Is Checked
The syntax invariance statements (5) and (6) are stated over a verification clause schedule of bound , a data size , and finite words of cells in related by cell word replacements and rewriting reachability. The region ownership statement (7) and head uniqueness statement (8) are stated over a coherent sequence of cells in , with the exterior boundary condition and a non-idle cell for (7) and with two same-region active head indices for (8). The region core statement (9) is stated over a sequence of cells in rigid block layout and a cell index satisfying the local skeleton and cell hypotheses for region blocks, quantified over block offsets up to the cell’s arity and core positions below .