OctoInformBeta

OpenAI preprint, September 2026 · §2. A hierarchy defined by finite local rules

Lemma 2.1: Over nontrivial rings, rewriting governs vanishing and equality, homogeneity with nonempty zero words gives nontriviality, and finite tables at height h≥4h \ge 4 are homogeneous

Homogeneous word rewriting tables preserve length and grade their algebras.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take an alphabet α\alpha, a binary replacement rule on finite words over α\alpha, and a collection of declared zero words. Quotienting the free associative algebra over a ring KK 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 10000h10000h for a height parameter hh.

Word Rewriting Tables and Their Algebras

For an alphabet α\alpha, the free monoid of words W(α)W(\alpha) consists of finite strings of letters from α\alpha under concatenation, with identity 11 (the empty word), word length |w||w| for w∈W(α)w \in W(\alpha), and one-letter and two-letter words written [a][a] and [a,b][a, b]. Given a ring KK, the monoid algebra K[W(α)]K[W(\alpha)] is the associative KK-algebra of formal KK-linear combinations of words in W(α)W(\alpha)✦, in which each word w∈W(α)w \in W(\alpha) has a basis monomial ew∈K[W(α)]e_w \in K[W(\alpha)] with coefficient 11 at ww and 00 elsewhere.✦

A word rewriting table T=(RT,ZT)T = (R_T, Z_T) over α\alpha consists of a binary replacement relation RT⊆W(α)×W(α)R_T \subseteq W(\alpha) \times W(\alpha) and a set ZT⊆W(α)Z_T \subseteq W(\alpha) of zero words.✦ For a ring KK, the defining relations of TT in K[W(α)]K[W(\alpha)] form the set {ev−ew:(v,w)∈RT}∪{ez:z∈ZT},\{e_v - e_w : (v, w) \in R_T\} \cup \{e_z : z \in Z_T\},(1)✦ and the defining two-sided ideal I(T,K)⊆K[W(α)]I(T, K) \subseteq K[W(\alpha)] is the two-sided ideal generated by (1).✦ The algebra of the rewriting table TT over KK is the quotient ring A(T,K)=K[W(α)]/I(T,K)A(T, K) = K[W(\alpha)] / I(T, K)✦, with quotient ring homomorphism π:K[W(α)]→A(T,K)\pi : K[W(\alpha)] \to A(T, K) sending each basis monomial ewe_w to the word element w‾=π(ew)∈A(T,K)\bar{w} = \pi(e_w) \in A(T, K).

The replacement reachability relation ∼T\sim_T on W(α)W(\alpha) is the monoid congruence generated by RTR_T✦, and a word w∈W(α)w \in W(\alpha) vanishes in TT if there exist words p,z,s∈W(α)p, z, s \in W(\alpha) with z∈ZTz \in Z_T such that w∼Tpzsw \sim_T p z s.✦ A word rewriting table TT is homogeneous if |v|=|w||v| = |w| for every pair (v,w)∈RT(v, w) \in R_T.✦ Given a table TT and a ring KK, the word grading homomorphism γ0:W(α)→A(T,K)[X]\gamma_0 : W(\alpha) \to A(T, K)[X] into the polynomial ring over A(T,K)A(T, K) is the monoid homomorphism defined by (2): γ0(w)=w‾X|w|.\gamma_0(w) = \bar{w} X^{|w|}.(2)✦

Finite Table Cells and the Algebra Table

Let q,k∈ℕq, k \in \mathbb{N} be bounds. The set of block cell positions Pos(q)\mathrm{Pos}(q) of bound qq consists of the core positions core(p)\mathrm{core}(p) (0≤p<q0 \le p < q), the palette positions palette(a)\mathrm{palette}(a) (0≤a<q0 \le a < q), and the terminal position stop\mathrm{stop}, and a cell marker is one of five tags: idle\mathrm{idle}, left\mathrm{left}, boundary\mathrm{boundary}, full\mathrm{full}, or right\mathrm{right}. A block metadata record of arity bound kk is a triple (a,z,b)(a, z, b) consisting of an arity 0≤a<k0 \le a < k, a Boolean zero-task flag z∈{false,true}z \in \{\mathrm{false}, \mathrm{true}\}, and a block index 0≤b≤a0 \le b \le a.✦ A verification task specification is a pair (a,z)(a, z) with 0≤a<100 \le a < 10 and z∈{false,true}z \in \{\mathrm{false}, \mathrm{true}\}✦; for arity bound k=10k = 10, a cell arity metadata record (a,z,b)(a, z, b) determines the verification task (a,z)(a, z), and the default cell metadata is (0,false,0)(0, \mathrm{false}, 0).

A cell syntactic skeleton ss of position bound qq and arity bound kk consists of a position in Pos(q)\mathrm{Pos}(q), a cell marker, and a block metadata record of arity bound kk✦; updating the marker of ss with a marker mm yields the skeleton μ(s,m)\mu(s, m) having marker mm and the same position and metadata.✦ A skeleton ss is initial if its block index is 00 and its position is core(0)\mathrm{core}(0), and terminal if its block index equals its arity and its position is stop\mathrm{stop}. A skeleton ss is admissible if its marker is never right\mathrm{right} when ss is initial and never left\mathrm{left} when ss is terminal✦, and a skeleton ss carries an active head marker if its marker is boundary\mathrm{boundary} or full\mathrm{full}.

Two skeletons aa and bb of bounds q,kq, k satisfy structural position adjacency if their positions are (core(p),core(r))(\mathrm{core}(p), \mathrm{core}(r)) with p+1=rp + 1 = r, (core(p),palette(c))(\mathrm{core}(p), \mathrm{palette}(c)) with p+1=qp + 1 = q, (palette(c),palette(c′))(\mathrm{palette}(c), \mathrm{palette}(c')), (palette(c),stop)(\mathrm{palette}(c), \mathrm{stop}), or (stop,core(0))(\mathrm{stop}, \mathrm{core}(0)).✦ Two skeletons aa and bb satisfy internal consistency if they have the same arity and zero-task flag, the block index of bb is one more than that of aa when aa has position stop\mathrm{stop} and equals that of aa otherwise, bb is not initial, and aa is not terminal.✦ A skeleton ss is left-external if its marker is idle\mathrm{idle}, or its marker is not right\mathrm{right} and ss is initial✦; a skeleton ss is right-external if its marker is idle\mathrm{idle} or boundary\mathrm{boundary}, or its marker is not left\mathrm{left} and ss is terminal.✦ A skeleton ss accepts a marker mm on the left if m∈{full,right}m \in \{\mathrm{full}, \mathrm{right}\} when the marker of ss is right\mathrm{right} and m=leftm = \mathrm{left} otherwise✦, and ss accepts mm on the right if m∈{left,boundary,full}m \in \{\mathrm{left}, \mathrm{boundary}, \mathrm{full}\} when the marker of ss is left\mathrm{left} and m=rightm = \mathrm{right} otherwise.✦ Two skeletons aa and bb form a compatible adjacent skeleton pair if they satisfy structural position adjacency and either aa is right-external while bb is left-external, or neither aa is right-external nor bb is left-external, aa accepts the marker of bb on the right, bb accepts the marker of aa on the left, and aa and bb satisfy internal consistency.✦

For a color set CC, the set of palette checker states Check(C)\mathrm{Check}(C) consists of idle\mathrm{idle}, passed(x)\mathrm{passed}(x) for each color x∈Cx \in C, and an active head head(x)\mathrm{head}(x) seeking x∈Cx \in C.✦ Two adjacent checker states in Check(C)\mathrm{Check}(C) form a compatible checker pair if they are (idle,idle)(\mathrm{idle}, \mathrm{idle}), (passed(x),passed(x))(\mathrm{passed}(x), \mathrm{passed}(x)), (passed(x),head(x))(\mathrm{passed}(x), \mathrm{head}(x)), or (head(x),idle)(\mathrm{head}(x), \mathrm{idle}) for some x∈Cx \in C.✦ A checker state in Check(C)\mathrm{Check}(C) satisfies the terminal checker condition if it is idle\mathrm{idle} or head(x)\mathrm{head}(x) for some x∈Cx \in C, and fails it when in a passed(x)\mathrm{passed}(x) state.✦

For a bound q∈ℕq \in \mathbb{N}, a cell memory address is either a data address data(s,b,p)\mathrm{data}(s, b, p) specified by a Boolean side s∈{false,true}s \in \{\mathrm{false}, \mathrm{true}\}, a block index 0≤b<100 \le b < 10, and a position index 0≤p<q0 \le p < q, or a certificate address cert(p)\mathrm{cert}(p) with 0≤p<q0 \le p < q.✦ A three-bit register state r∈ℛr \in \mathcal{R} is a map {0,1,2}→𝔽2\{0, 1, 2\} \to \mathbb{F}_2, with addition taken pointwise in 𝔽2\mathbb{F}_2.✦ 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 qq is a tuple (s,j,p,r)(s, j, p, r) consisting of a Boolean side ss, a clause index 0≤j<q0 \le j < q, a head computation phase pp, and a register r∈ℛr \in \mathcal{R}✦, with default head state (false,0,acquisition,0)(\mathrm{false}, 0, \text{acquisition}, 0). A verification clause CC of bound qq consists of three cell memory addresses a0,a1,a2a_0, a_1, a_2 of bound qq and a Boolean truth function τC:ℛ→{false,true}\tau_C : \mathcal{R} \to \{\mathrm{false}, \mathrm{true}\}.✦ A verification clause schedule SS of bound qq specifies for each task tt a positive clause count 1≤nS(t)≤q1 \le n_S(t) \le q together with a family of verification clauses CS(t,j)C_S(t, j) indexed by task tt and clause index 0≤j<q0 \le j < q.✦

A finite table cell cc of bound qq in 𝒞q\mathcal{C}_q consists of a syntactic skeleton scs_c of position bound qq and arity bound 1010, a palette checker state χc∈Check({0,…,q−1})\chi_c \in \mathrm{Check}(\{0, \dots, q - 1\}), a pair of data bits datac:{false,true}→𝔽2\mathrm{data}_c : \{\mathrm{false}, \mathrm{true}\} \to \mathbb{F}_2, a certificate bit certc∈𝔽2\mathrm{cert}_c \in \mathbb{F}_2, and a reading head state hch_c of bound qq.✦ The position, marker, and metadata of a cell cc are those of its skeleton scs_c, with task tct_c determined by its metadata; the cell cc is in the core if its position is core(p)\mathrm{core}(p) for some p<qp < q, in the palette if its position is palette(a)\mathrm{palette}(a) for some a<qa < q, and head-free if scs_c does not carry an active head marker and χc\chi_c is not head(x)\mathrm{head}(x) for any x<qx < q. Reading a cell memory address aa from a cell cc yields a bit in 𝔽2\mathbb{F}_2: it returns 00 unless cc has position core(r)\mathrm{core}(r) for some r<qr < q, in which case a data address data(s,b,p)\mathrm{data}(s, b, p) returns datac(s)\mathrm{data}_c(s) when r=pr = p and the block index of cc equals bb (and 00 otherwise), while a certificate address cert(p)\mathrm{cert}(p) returns certc\mathrm{cert}_c when r=pr = p and the block index of cc is 00 (and 00 otherwise).✦ Given a verification clause CC with addresses a0,a1,a2a_0, a_1, a_2 and a cell c∈𝒞qc \in \mathcal{C}_q, the clause register delta Δ(C,c)∈ℛ\Delta(C, c) \in \mathcal{R} is the register whose ii-th entry is the bit read from cc at aia_i for i∈{0,1,2}i \in \{0, 1, 2\}.✦

Given a schedule SS of bound qq and a data size d∈ℕd \in \mathbb{N}, a cell c∈𝒞qc \in \mathcal{C}_q satisfies the cell formatting condition if: its skeleton scs_c is admissible; its checker state χc\chi_c is idle\mathrm{idle} whenever cc is not in the palette; datac\mathrm{data}_c vanishes identically at any core position core(p)\mathrm{core}(p) with p≥dp \ge d; both datac\mathrm{data}_c and certc\mathrm{cert}_c vanish whenever cc is not in the core; a marker idle\mathrm{idle} forces default metadata, default head state, datac(true)=0\mathrm{data}_c(\mathrm{true}) = 0, and certc=0\mathrm{cert}_c = 0; a marker left\mathrm{left} or right\mathrm{right} forces the default head state; a marker boundary\mathrm{boundary} forces head clause 00, phase acquisition, and zero register; an active head marker with zero-task flag true\mathrm{true} forces head side false\mathrm{false}; and a marker full\mathrm{full} requires head clause 00 in phase success, head clause strictly less than nS(tc)n_S(t_c) in every other phase, and terminal skeleton scs_c in every endpoint phase.✦ Two cells a,b∈𝒞qa, b \in \mathcal{C}_q satisfy checker compatibility if χa\chi_a and χb\chi_b form a compatible checker pair whenever both aa and bb are in the palette, and χa\chi_a satisfies the terminal checker condition whenever aa is in the palette and bb has position stop\mathrm{stop}.✦ Two cells a,b∈𝒞qa, b \in \mathcal{C}_q form a compatible adjacent cell pair if their skeletons sas_a and sbs_b form a compatible adjacent skeleton pair and aa and bb satisfy checker compatibility.✦

For a cell c∈𝒞qc \in \mathcal{C}_q, a Boolean side ss, a marker mm, a clause index 0≤j<q0 \le j < q, a phase pp, a register r∈ℛr \in \mathcal{R}, a checker state χ∈Check({0,…,q−1})\chi \in \mathrm{Check}(\{0, \dots, q - 1\}), and a color y<qy < q, six local updates modify cc as follows: the boundary cell cbd(s)c_{\mathrm{bd}}(s) marks scs_c with boundary\mathrm{boundary} and sets hch_c to the default head with side ss✦; the wing cell cwing(m)c_{\mathrm{wing}}(m) marks scs_c with mm and resets hch_c to the default head✦; the full cell cfull(s,j,p,r)c_{\mathrm{full}}(s, j, p, r) marks scs_c with full\mathrm{full} and sets hch_c to (s,j,p,r)(s, j, p, r)✦; the idle cell cidle(s)c_{\mathrm{idle}}(s) preserves the position of cc, resets its marker to idle\mathrm{idle}, its metadata to the default metadata, its head to the default head, and its certificate to 00, and sets its data bits to datac(s)\mathrm{data}_c(s) on side false\mathrm{false} and 00 on side true\mathrm{true}✦; updating the checker state yields σchk(c,χ)\sigma_{\mathrm{chk}}(c, \chi) by replacing only the checker state of cc with χ\chi✦; and updating the palette color yields σcol(c,y)\sigma_{\mathrm{col}}(c, y) by replacing only the skeleton position of cc with palette(y)\mathrm{palette}(y).

Given a verification clause schedule SS of bound qq, the unary cell transition relates a cell before and after a boundary step across twelve rules (for a cell c∈𝒞qc \in \mathcal{C}_q, Boolean side ss, clause indices j,j′<qj, j' < q, and register r∈ℛr \in \mathcal{R}): from cidle(s)c_{\mathrm{idle}}(s) to cbd(s)c_{\mathrm{bd}}(s) when scs_c is initial; from cbd(s)c_{\mathrm{bd}}(s) to cfull(s,0,acquisition,0)c_{\mathrm{full}}(s, 0, \text{acquisition}, 0) when scs_c is terminal; from cfull(s,j,p,r)c_{\mathrm{full}}(s, j, p, r) to cfull(s,j,p′,r)c_{\mathrm{full}}(s, j, p', r) along the phase steps acquisition→read-left\text{acquisition} \to \text{read-left} (terminal scs_c), read-left→read-right\text{read-left} \to \text{read-right} (initial scs_c), read-right→before-gate\text{read-right} \to \text{before-gate} (terminal scs_c), after-gate→undo-left\text{after-gate} \to \text{undo-left} (terminal scs_c), undo-left→undo-right\text{undo-left} \to \text{undo-right} (initial scs_c), and undo-right→finish\text{undo-right} \to \text{finish} (terminal scs_c); from cfull(s,j,before-gate,r)c_{\mathrm{full}}(s, j, \text{before-gate}, r) to cfull(s,j,after-gate,r)c_{\mathrm{full}}(s, j, \text{after-gate}, r) when scs_c is terminal and τCS(tc,j)(r)=true\tau_{C_S(t_c, j)}(r) = \mathrm{true}; from cfull(s,j,finish,0)c_{\mathrm{full}}(s, j, \text{finish}, 0) to cfull(s,j′,acquisition,0)c_{\mathrm{full}}(s, j', \text{acquisition}, 0) when scs_c is terminal and j′=j+1j' = j + 1; from cfull(s,j,finish,0)c_{\mathrm{full}}(s, j, \text{finish}, 0) to cfull(s,0,success,0)c_{\mathrm{full}}(s, 0, \text{success}, 0) when scs_c is terminal and j+1=nS(tc)j + 1 = n_S(t_c); and from cfull(s,0,success,0)c_{\mathrm{full}}(s, 0, \text{success}, 0) to cfull(¬s,0,success,0)c_{\mathrm{full}}(\neg s, 0, \text{success}, 0) when scs_c is terminal and the zero-task flag of cc is false\mathrm{false}.✦ Under the same schedule SS, the binary cell transition relates an adjacent cell pair before and after a move across eight local rules (for cells a,b∈𝒞qa, b \in \mathcal{C}_q, Boolean side ss, clause index j<qj < q, register r∈ℛr \in \mathcal{R}, and colors x,y,v<qx, y, v < q): acquiring an idle neighbor from (abd(s),bidle(s))(a_{\mathrm{bd}}(s), b_{\mathrm{idle}}(s)) to (awing(left),bbd(s))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{bd}}(s)) when μ(sa,left)\mu(s_a, \mathrm{left}) and μ(sb,boundary)\mu(s_b, \mathrm{boundary}) form a compatible skeleton pair; reading left from (awing(left),bfull(s,j,read-left,r))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{read-left}, r)) to (afull(s,j,read-left,r+Δ(CS(ta,j),a)),bwing(right))(a_{\mathrm{full}}(s, j, \text{read-left}, r + \Delta(C_S(t_a, j), a)), b_{\mathrm{wing}}(\mathrm{right})) and reading right from (afull(s,j,read-right,r),bwing(right))(a_{\mathrm{full}}(s, j, \text{read-right}, r), b_{\mathrm{wing}}(\mathrm{right})) to (awing(left),bfull(s,j,read-right,r))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{read-right}, r)), both when μ(sa,full)\mu(s_a, \mathrm{full}) and μ(sb,right)\mu(s_b, \mathrm{right}) form a compatible skeleton pair; undoing left from (awing(left),bfull(s,j,undo-left,r))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{undo-left}, r)) to (afull(s,j,undo-left,r),bwing(right))(a_{\mathrm{full}}(s, j, \text{undo-left}, r), b_{\mathrm{wing}}(\mathrm{right})) and undoing right from (afull(s,j,undo-right,r),bwing(right))(a_{\mathrm{full}}(s, j, \text{undo-right}, r), b_{\mathrm{wing}}(\mathrm{right})) to (awing(left),bfull(s,j,undo-right,r+Δ(CS(ta,j),a)))(a_{\mathrm{wing}}(\mathrm{left}), b_{\mathrm{full}}(s, j, \text{undo-right}, r + \Delta(C_S(t_a, j), a))), both under the same full\mathrm{full} and right\mathrm{right} skeleton compatibility; creating a checker head from (a,σchk(b,idle))(a, \sigma_{\mathrm{chk}}(b, \mathrm{idle})) to (a,σchk(b,head(x)))(a, \sigma_{\mathrm{chk}}(b, \mathrm{head}(x))) when aa has position core(p)\mathrm{core}(p) with p+1=qp + 1 = q and bb is in the palette; advancing a checker head from (σchk(a,head(x)),σchk(b,idle))(\sigma_{\mathrm{chk}}(a, \mathrm{head}(x)), \sigma_{\mathrm{chk}}(b, \mathrm{idle})) to (σchk(a,passed(x)),σchk(b,head(x)))(\sigma_{\mathrm{chk}}(a, \mathrm{passed}(x)), \sigma_{\mathrm{chk}}(b, \mathrm{head}(x))) when aa has position palette(v)\mathrm{palette}(v) with v≠xv \neq x and bb is in the palette; and swapping (a,b)(a, b) to (b,a)(b, a) when aa and bb are head-free cells at positions palette(x)\mathrm{palette}(x) and palette(y)\mathrm{palette}(y) satisfying σcol(a,y)=b\sigma_{\mathrm{col}}(a, y) = b.✦ Given SS and a data size d∈ℕd \in \mathbb{N}, two cell lists vv and ww satisfy the cell list replacement relation if every cell appearing in vv or ww satisfies the cell formatting condition for SS and dd, and either v=[a]v = [a] and w=[b]w = [b] are singletons related in either direction by a unary cell transition, or v=[a,b]v = [a, b] and w=[a′,b′]w = [a', b'] are two-cell lists related in either direction by a binary cell transition.✦

Given a schedule SS of bound qq, a cell c∈𝒞qc \in \mathcal{C}_q satisfies the semantic zero cell condition if its marker is full\mathrm{full} and one of three failure conditions holds for its head hc=(s,j,p,r)h_c = (s, j, p, r): the phase pp is acquisition, finish, or success while r≠0r \neq 0; the phase pp is after-gate while τCS(tc,j)(r)=false\tau_{C_S(t_c, j)}(r) = \mathrm{false}; or the phase pp is success while the zero-task flag of cc is true\mathrm{true}.✦ Given SS and a data size d∈ℕd \in \mathbb{N}, a cell c∈𝒞qc \in \mathcal{C}_q satisfies the unary zero cell condition if cc fails the cell formatting condition for SS and dd, satisfies the semantic zero cell condition for SS, or has position palette(x)\mathrm{palette}(x) and checker state passed(x)\mathrm{passed}(x) for some x<qx < q.✦ Two cells a,b∈𝒞qa, b \in \mathcal{C}_q satisfy the binary zero cell condition if they do not form a compatible adjacent cell pair, if both have the same palette position palette(x)\mathrm{palette}(x), or if aa has position palette(x)\mathrm{palette}(x) and checker state head(y)\mathrm{head}(y) with x≠yx \neq y while bb has position stop\mathrm{stop}.✦

For a height parameter h∈ℕh \in \mathbb{N}, the raw bitstring alphabet ℬh\mathcal{B}_h consists of all Boolean vectors {0,…,10000h−1}→{false,true}\{0, \dots, 10000h - 1\} \to \{\mathrm{false}, \mathrm{true}\} of length 10000h10000h.✦ When h>0h > 0, cell encoding ench:𝒞2h→ℬh\mathrm{enc}_h : \mathcal{C}_{2^h} \to \mathcal{B}_h maps each cell of capacity 2h2^h to a raw bitstring; cell decoding dech\mathrm{dec}_h parses a raw bitstring w∈ℬhw \in \mathcal{B}_h to a candidate cell cc and yields cc if ench(c)=w\mathrm{enc}_h(c) = w (and is undefined otherwise)✦, while word decoding dech*\mathrm{dec}_h^* applies dech\mathrm{dec}_h letterwise to a word in W(ℬh)W(\mathcal{B}_h) and is undefined if any letter fails to decode.✦ Given h>0h > 0, a verification clause schedule SS of capacity 2h2^h, and a data size d∈ℕd \in \mathbb{N}, two raw words v,w∈W(ℬh)v, w \in W(\mathcal{B}_h) satisfy the raw word replacement relation if dech*\mathrm{dec}_h^* maps vv and ww to cell lists satisfying the cell list replacement relation for SS and dd.✦ Under the same parameters, a raw letter a∈ℬha \in \mathcal{B}_h satisfies the raw unary zero condition if dech\mathrm{dec}_h is undefined on aa or decodes aa to a cell satisfying the unary zero cell condition for SS and dd✦, and two raw letters a,b∈ℬha, b \in \mathcal{B}_h satisfy the raw binary zero condition if dech\mathrm{dec}_h maps both to cells satisfying the binary zero cell condition.✦ A raw word v∈W(ℬh)v \in W(\mathcal{B}_h) satisfies the zero raw word condition if v=[a]v = [a] for a letter aa satisfying the raw unary zero condition or v=[a,b]v = [a, b] for letters a,ba, b satisfying the raw binary zero condition.✦ The algebra table 𝒯(h,S,d)\mathcal{T}(h, S, d) of the schedule is the word rewriting table over ℬh\mathcal{B}_h 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 α\alpha be an alphabet, T=(RT,ZT)T = (R_T, Z_T) a word rewriting table over α\alpha, and KK a ring. If KK is nontrivial, then for every word w∈W(α)w \in W(\alpha), w‾=0 in A(T,K)⇔w vanishes in T;\bar{w} = 0 \text{ in } A(T, K) \iff w \text{ vanishes in } T;(3)✦ for any words v,w∈W(α)v, w \in W(\alpha), v‾=w‾ in A(T,K)⇔v∼Tw or both v and w vanish in T;\bar{v} = \bar{w} \text{ in } A(T, K) \iff v \sim_T w \text{ or both } v \text{ and } w \text{ vanish in } T;(4)✦ and whenever w∈W(α)w \in W(\alpha) does not vanish in TT, w‾≠0 in A(T,K).\bar{w} \neq 0 \text{ in } A(T, K).(5)✦ Suppose TT is homogeneous. If 1∉ZT1 \notin Z_T, then 1 does not vanish in T,1 \text{ does not vanish in } T,(6)✦ and if KK is also nontrivial, then A(T,K)≠{0}.A(T, K) \neq \{0\}.(7)✦ Moreover, for any words v,w∈W(α)v, w \in W(\alpha) satisfying v∼Twv \sim_T w, |v|=|w|,|v| = |w|,(8)✦ and there exists a KK-algebra grading homomorphism γ:A(T,K)→A(T,K)[X].\gamma : A(T, K) \to A(T, K)[X].(9)✦ Finally, for any integer h≥4h \ge 4, any verification clause schedule SS of capacity 2h2^h, and any data size d∈ℕd \in \mathbb{N}, 𝒯(h,S,d) is homogeneous.\mathcal{T}(h, S, d) \text{ is homogeneous}.(10)✦

In the paper, the result reads: for a word rewriting presentation T=(RT,ZT)T = (R_T, Z_T) of this kind over a field KK, the nonzero replacement classes of words under ∼T\sim_T form a KK-basis of A(T,K)A(T, K); a replacement class is zero precisely when one of its words contains an elementary zero-declared substring in ZTZ_T; the empty word 11 is one of the surviving classes; and A(T,K)A(T, K) is graded by word length. Instead of a KK-basis over a field, (3), (4), (5), and (7) work over any nontrivial ring KK, (6), (8), and (9) hold over an arbitrary ring KK once TT is homogeneous, and (10) supplies homogeneity for 𝒯(h,S,d)\mathcal{T}(h, S, d).

What Is Checked

The claims above are stated over an arbitrary alphabet α\alpha, a word rewriting table T=(RT,ZT)T = (R_T, Z_T) on W(α)W(\alpha), and a ring KK (assumed nontrivial in (3), (4), (5), and (7)), together with, for (10), any integer h≥4h \ge 4, any verification clause schedule SS of capacity 2h2^h, and any data size d∈ℕd \in \mathbb{N} defining the algebra table 𝒯(h,S,d)\mathcal{T}(h, S, d) over the raw bitstring alphabet ℬh\mathcal{B}_h.