The Setting
Take an alphabet , a binary replacement rule on finite words over , and a collection of declared zero words. Quotienting the free associative algebra over a ring by the relations equating replaceable pairs and killing all zero words yields a finitely presented algebra whose elements are linear combinations of words. Two structural questions arise immediately: when do two words represent the same element or zero in this quotient, and when does the resulting algebra remain nontrivial and carry a grading by word length?
A concrete instance of this construction arises from local transition rules on finite arrays of machine cells encoding bounded clause verification schedules. Each cell carries a syntactic skeleton, a palette color checker, data and certificate bits, and a reading head, and is encoded as a raw bitstring of length for a height parameter .
Word Rewriting Tables and Their Algebras
For an alphabet , the free monoid of words consists of finite strings of letters from under concatenation, with identity (the empty word), word length for , and one-letter and two-letter words written and . Given a ring , the monoid algebra is the associative -algebra of formal -linear combinations of words in ✦, in which each word has a basis monomial with coefficient at and elsewhere.✦
A word rewriting table over consists of a binary replacement relation and a set of zero words.✦ For a ring , the defining relations of in form the set (1)✦ and the defining two-sided ideal is the two-sided ideal generated by (1).✦ The algebra of the rewriting table over is the quotient ring ✦, with quotient ring homomorphism sending each basis monomial to the word element .
The replacement reachability relation on is the monoid congruence generated by ✦, and a word vanishes in if there exist words with such that .✦ A word rewriting table is homogeneous if for every pair .✦ Given a table and a ring , the word grading homomorphism into the polynomial ring over is the monoid homomorphism defined by (2): (2)✦
Finite Table Cells and the Algebra Table
Let be bounds. The set of block cell positions of bound consists of the core positions (), the palette positions (), and the terminal position , and a cell marker is one of five tags: , , , , or . A block metadata record of arity bound is a triple consisting of an arity , a Boolean zero-task flag , and a block index .✦ A verification task specification is a pair with and ✦; for arity bound , a cell arity metadata record determines the verification task , and the default cell metadata is .
A cell syntactic skeleton of position bound and arity bound consists of a position in , a cell marker, and a block metadata record of arity bound ✦; updating the marker of with a marker yields the skeleton having marker and the same position and metadata.✦ A skeleton is initial if its block index is and its position is , and terminal if its block index equals its arity and its position is . A skeleton is admissible if its marker is never when is initial and never when is terminal✦, and a skeleton carries an active head marker if its marker is or .
Two skeletons and of bounds satisfy structural position adjacency if their positions are with , with , , , or .✦ Two skeletons and satisfy internal consistency if they have the same arity and zero-task flag, the block index of is one more than that of when has position and equals that of otherwise, is not initial, and is not terminal.✦ A skeleton is left-external if its marker is , or its marker is not and is initial✦; a skeleton is right-external if its marker is or , or its marker is not and is terminal.✦ A skeleton accepts a marker on the left if when the marker of is and otherwise✦, and accepts on the right if when the marker of is and otherwise.✦ Two skeletons and form a compatible adjacent skeleton pair if they satisfy structural position adjacency and either is right-external while is left-external, or neither is right-external nor is left-external, accepts the marker of on the right, accepts the marker of on the left, and and satisfy internal consistency.✦
For a color set , the set of palette checker states consists of , for each color , and an active head seeking .✦ Two adjacent checker states in form a compatible checker pair if they are , , , or for some .✦ A checker state in satisfies the terminal checker condition if it is or for some , and fails it when in a state.✦
For a bound , a cell memory address is either a data address specified by a Boolean side , a block index , and a position index , or a certificate address with .✦ A three-bit register state is a map , with addition taken pointwise in .✦ A head computation phase is one of nine sequential stages: acquisition, read-left, read-right, before-gate, after-gate, undo-left, undo-right, finish, or success✦, of which acquisition, before-gate, after-gate, finish, and success are endpoint phases.✦ A reading head state of bound is a tuple consisting of a Boolean side , a clause index , a head computation phase , and a register ✦, with default head state . A verification clause of bound consists of three cell memory addresses of bound and a Boolean truth function .✦ A verification clause schedule of bound specifies for each task a positive clause count together with a family of verification clauses indexed by task and clause index .✦
A finite table cell of bound in consists of a syntactic skeleton of position bound and arity bound , a palette checker state , a pair of data bits , a certificate bit , and a reading head state of bound .✦ The position, marker, and metadata of a cell are those of its skeleton , with task determined by its metadata; the cell is in the core if its position is for some , in the palette if its position is for some , and head-free if does not carry an active head marker and is not for any . Reading a cell memory address from a cell yields a bit in : it returns unless has position for some , in which case a data address returns when and the block index of equals (and otherwise), while a certificate address returns when and the block index of is (and otherwise).✦ Given a verification clause with addresses and a cell , the clause register delta is the register whose -th entry is the bit read from at for .✦
Given a schedule of bound and a data size , a cell satisfies the cell formatting condition if: its skeleton is admissible; its checker state is whenever is not in the palette; vanishes identically at any core position with ; both and vanish whenever is not in the core; a marker forces default metadata, default head state, , and ; a marker or forces the default head state; a marker forces head clause , phase acquisition, and zero register; an active head marker with zero-task flag forces head side ; and a marker requires head clause in phase success, head clause strictly less than in every other phase, and terminal skeleton in every endpoint phase.✦ Two cells satisfy checker compatibility if and form a compatible checker pair whenever both and are in the palette, and satisfies the terminal checker condition whenever is in the palette and has position .✦ Two cells form a compatible adjacent cell pair if their skeletons and form a compatible adjacent skeleton pair and and satisfy checker compatibility.✦
For a cell , a Boolean side , a marker , a clause index , a phase , a register , a checker state , and a color , six local updates modify as follows: the boundary cell marks with and sets to the default head with side ✦; the wing cell marks with and resets to the default head✦; the full cell marks with and sets to ✦; the idle cell preserves the position of , resets its marker to , its metadata to the default metadata, its head to the default head, and its certificate to , and sets its data bits to on side and on side ✦; updating the checker state yields by replacing only the checker state of with ✦; and updating the palette color yields by replacing only the skeleton position of with .
Given a verification clause schedule of bound , the unary cell transition relates a cell before and after a boundary step across twelve rules (for a cell , Boolean side , clause indices , and register ): from to when is initial; from to when is terminal; from to along the phase steps (terminal ), (initial ), (terminal ), (terminal ), (initial ), and (terminal ); from to when is terminal and ; from to when is terminal and ; from to when is terminal and ; and from to when is terminal and the zero-task flag of is .✦ Under the same schedule , the binary cell transition relates an adjacent cell pair before and after a move across eight local rules (for cells , Boolean side , clause index , register , and colors ): acquiring an idle neighbor from to when and form a compatible skeleton pair; reading left from to and reading right from to , both when and form a compatible skeleton pair; undoing left from to and undoing right from to , both under the same and skeleton compatibility; creating a checker head from to when has position with and is in the palette; advancing a checker head from to when has position with and is in the palette; and swapping to when and are head-free cells at positions and satisfying .✦ Given and a data size , two cell lists and satisfy the cell list replacement relation if every cell appearing in or satisfies the cell formatting condition for and , and either and are singletons related in either direction by a unary cell transition, or and are two-cell lists related in either direction by a binary cell transition.✦
Given a schedule of bound , a cell satisfies the semantic zero cell condition if its marker is and one of three failure conditions holds for its head : the phase is acquisition, finish, or success while ; the phase is after-gate while ; or the phase is success while the zero-task flag of is .✦ Given and a data size , a cell satisfies the unary zero cell condition if fails the cell formatting condition for and , satisfies the semantic zero cell condition for , or has position and checker state for some .✦ Two cells satisfy the binary zero cell condition if they do not form a compatible adjacent cell pair, if both have the same palette position , or if has position and checker state with while has position .✦
For a height parameter , the raw bitstring alphabet consists of all Boolean vectors of length .✦ When , cell encoding maps each cell of capacity to a raw bitstring; cell decoding parses a raw bitstring to a candidate cell and yields if (and is undefined otherwise)✦, while word decoding applies letterwise to a word in and is undefined if any letter fails to decode.✦ Given , a verification clause schedule of capacity , and a data size , two raw words satisfy the raw word replacement relation if maps and to cell lists satisfying the cell list replacement relation for and .✦ Under the same parameters, a raw letter satisfies the raw unary zero condition if is undefined on or decodes to a cell satisfying the unary zero cell condition for and ✦, and two raw letters satisfy the raw binary zero condition if maps both to cells satisfying the binary zero cell condition.✦ A raw word satisfies the zero raw word condition if for a letter satisfying the raw unary zero condition or for letters satisfying the raw binary zero condition.✦ The algebra table of the schedule is the word rewriting table over whose replacement relation is the raw word replacement relation and whose zero word set consists of the raw words satisfying the zero raw word condition.✦
The Claim
Theorem 1. Let be an alphabet, a word rewriting table over , and a ring. If is nontrivial, then for every word , (3)✦ for any words , (4)✦ and whenever does not vanish in , (5)✦ Suppose is homogeneous. If , then (6)✦ and if is also nontrivial, then (7)✦ Moreover, for any words satisfying , (8)✦ and there exists a -algebra grading homomorphism (9)✦ Finally, for any integer , any verification clause schedule of capacity , and any data size , (10)✦
In the paper, the result reads: for a word rewriting presentation of this kind over a field , the nonzero replacement classes of words under form a -basis of ; a replacement class is zero precisely when one of its words contains an elementary zero-declared substring in ; the empty word is one of the surviving classes; and is graded by word length. Instead of a -basis over a field, (3), (4), (5), and (7) work over any nontrivial ring , (6), (8), and (9) hold over an arbitrary ring once is homogeneous, and (10) supplies homogeneity for .
What Is Checked
The claims above are stated over an arbitrary alphabet , a word rewriting table on , and a ring (assumed nontrivial in (3), (4), (5), and (7)), together with, for (10), any integer , any verification clause schedule of capacity , and any data size defining the algebra table over the raw bitstring alphabet .