OctoInformBeta

OpenAI preprint, September 2026 · §2. Forced occurrence counts · §2

§2 (setting): preprocessing, blocking and the count recursion: Preprocessing and blocking define an exact recursion with periodic lower bounds

Forced counts from finite substring data.

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

A shortest common superstring instance is a finite list SS of finite words over a symbol alphabet 𝒜\mathcal A. The count construction assigns a natural number to each substring, subject to requirements from input words, their extensions and periodic texts. Word lengths count symbols.

Write s≼Ts\preceq T for contiguous substring containment, including the empty word ε\varepsilon. An occurrence of a word ss in a word TT is a starting position x∈ℕx\in\mathbb N satisfying (1); overlapping occurrences have distinct starting positions. Occ⁡(T,s,x)⇔x+|s|≤|T| and Tx+i=si(0≤i<|s|).\operatorname{Occ}(T,s,x) \quad\Longleftrightarrow\quad x+|s|\le |T|\ \text{ and }\ T_{x+i}=s_i\quad(0\le i<|s|).(1)✦ For a word ss, write s[a:b)s[a:b) for its substring in positions a,…,b−1a,\ldots,b-1. The substring set Sub⁡(s)\operatorname{Sub}(s) of a word ss and the irreducible input set R(S)R(S) are the finite sets in (2) and (3). Sub⁡(s)={s[a:b):0≤a≤b≤|s|}.\operatorname{Sub}(s)=\{s[a:b):0\le a\le b\le |s|\}.(2)✦ R(S)={s∈S:s≠ε,s≼t⇒t=s for every t∈S}.R(S)=\{s\in S:s\ne\varepsilon,\quad s\preceq t\Longrightarrow t=s\ \text{ for every }t\in S\}.(3)✦ The substring vertex set V(S)V(S) of SS is the set of words in (4), and the input alphabet Σ(S)\Sigma(S) of SS is the symbol set in (5). V(S)={ε}∪⋃s∈SSub⁡(s).V(S)=\{\varepsilon\}\cup\bigcup_{s\in S}\operatorname{Sub}(s).(4)✦ Σ(S)={c∈𝒜:c occurs in some s∈S}.\Sigma(S)=\{c\in\mathcal A:c\text{ occurs in some }s\in S\}.(5)✦ A finite count instance D=(V,R,Σ)D=(V,R,\Sigma) consists of finite sets of words VV and RR, and a finite set of symbols Σ\Sigma.✦ The preprocessed instance D(S)D(S) associated with SS is the finite count instance in (6). D(S)=(V(S),R(S),Σ(S)).D(S)=(V(S),R(S),\Sigma(S)).(6)✦

Blocking Occurrences

A template is an integer-indexed text A:ℤ→𝒜A:\mathbb Z\to\mathcal A. A word ss matches AA, written A⊨sA\models s, when it satisfies (7). A⊨s⇔si=A(i)(0≤i<|s|).A\models s\quad\Longleftrightarrow\quad s_i=A(i)\quad(0\le i<|s|).(7)✦ A blocking occurrence of a word ss in a word rr relative to a template AA is a starting position jj satisfying (8). Block⁡A(s,r,j)⇔1≤j,j+|s|<|r|,Occ⁡(r,s,j),rh=A(h−j)(0<h,h+1<|r|),r0≠A(−j),r|r|−1≠A(|r|−1−j).\begin{aligned} \operatorname{Block}_A(s,r,j)\quad\Longleftrightarrow\quad & 1\le j,\qquad j+|s|<|r|,\qquad \operatorname{Occ}(r,s,j),\\ &r_h=A(h-j)\quad(0<h,\ h+1<|r|),\\ &r_0\ne A(-j),\qquad r_{|r|-1}\ne A(|r|-1-j). \end{aligned}(8)✦ The blocking coefficient cA(s,r)c_A(s,r) counts the blocking positions, as in (9). For a count function mm, its blocking sum BA(s;m)B_A(s;m) over VV is defined by (10). cA(s,r)=|{j∈{0,…,|r|}:Block⁡A(s,r,j)}|.c_A(s,r)=\bigl|\{j\in\{0,\ldots,|r|\}: \operatorname{Block}_A(s,r,j)\}\bigr|.(9)✦ BA(s;m)=∑r∈VcA(s,r)m(r).B_A(s;m)=\sum_{r\in V}c_A(s,r)m(r).(10)✦

The Count Recursion

Fix a finite count instance D=(V,R,Σ)D=(V,R,\Sigma). The maximum vertex length HH of a finite count instance D=(V,R,Σ)D=(V,R,\Sigma) is the natural number given by H=max⁡({0}∪{|v|:v∈V})H=\max(\{0\}\cup\{|v|:v\in V\}).✦ For a natural number count function mm on words and a word ww, the left and right extension sums ℓD(w;m)\ell_D(w;m) and rD(w;m)r_D(w;m) are the sums in (11). ℓD(w;m)=∑c∈Σcw∈Vm(cw),rD(w;m)=∑c∈Σwc∈Vm(wc).\ell_D(w;m)=\sum_{\substack{c\in\Sigma\\cw\in V}}m(cw), \qquad r_D(w;m)=\sum_{\substack{c\in\Sigma\\wc\in V}}m(wc).(11) For a word vv over 𝒜\mathcal A, a chosen default symbol in 𝒜\mathcal A and a nonnegative integer pp, the generated template Av,p:ℤ→𝒜A_{v,p}:\mathbb Z\to\mathcal A takes at xx the symbol of vv indexed by the nonnegative part of the remainder of xx modulo pp, using the default symbol if that position is absent. When 0<p≤|v|0<p\le |v|, it repeats the first pp symbols of vv in both integer directions, as in (12). Av,p(x)=vxmod⁡p(x∈ℤ).A_{v,p}(x)=v_{x\bmod p}\qquad(x\in\mathbb Z).(12) For words w,vw,v and natural numbers p,kp,k, the periodic rule qD(w,v,p,k;m)q_D(w,v,p,k;m) is the bound in (13); parameters outside its stated conditions contribute zero. In the nonzero case, A=Av,pA=A_{v,p}. qD(w,v,p,k;m)={BA(w;m)+k+1,p>0,k>0,w≠ε,|w|+kp=|v|,A⊨v,A⊨w,BA(v;m)<m(v),0,otherwise.q_D(w,v,p,k;m)= \begin{cases} B_A(w;m)+k+1, &\begin{gathered} p>0,\ k>0,\ w\ne\varepsilon,\quad |w|+kp=|v|,\\ A\models v,\quad A\models w,\quad B_A(v;m)<m(v), \end{gathered}\\ 0,&\text{otherwise}. \end{cases}(13)✦ The maximum periodic rule bound QD(w;m)Q_D(w;m) is the finite maximum in (14). The recursion operator FDF_D is defined by (15), where 𝟏R\mathbf 1_R is the indicator of the required set RR. QD(w;m)=max⁡({0}∪{qD(w,v,p,k;m):v∈V,0≤p,k≤|v|}).Q_D(w;m)=\max\bigl(\{0\}\cup \{q_D(w,v,p,k;m):v\in V,\ 0\le p,k\le |v|\}\bigr).(14)✦ FD(m)(w)={max⁡{𝟏R(w),ℓD(w;m),rD(w;m),QD(w;m)},w∈V\{ε},0,otherwise.F_D(m)(w)= \begin{cases} \max\{\mathbf 1_R(w),\ell_D(w;m),r_D(w;m),Q_D(w;m)\}, &w\in V\setminus\{\varepsilon\},\\ 0,&\text{otherwise}. \end{cases}(15)✦ The count iteration starts at zero. For a word ww, the forced occurrence count m(w)m(w) of the finite count instance DD is the value at ww of the count iteration after H+1H+1 stages, as specified in (16). m0(w)=0,mn+1=FD(mn),m=mH+1.m_0(w)=0,\qquad m_{n+1}=F_D(m_n),\qquad m=m_{H+1}.(16) The total letter count WW is the sum of the one-letter forced counts in (17), where [c][c] denotes the one-letter word with symbol cc. W=∑c∈Σm([c]).W=\sum_{c\in\Sigma}m([c]).(17)✦

The Claim

Theorem 1. For every finite input list SS and every word TT, the irreducible input set satisfies (18). (s≼T for every s∈R(S))⇔(s≼T for every s∈S).\bigl(s\preceq T\text{ for every }s\in R(S)\bigr) \quad\Longleftrightarrow\quad \bigl(s\preceq T\text{ for every }s\in S\bigr).(18)✦ For every finite count instance DD, its forced counts satisfy the exact recursion (19) at every word ww. FD(m)(w)=m(w).F_D(m)(w)=m(w).(19)✦ Let AA be an integer-indexed text with positive period pp, let k>0k>0, and let w,v∈Vw,v\in V match AA. Suppose w≠εw\ne\varepsilon, |w|+kp=|v||w|+kp=|v|, and BA(v;m)<m(v)B_A(v;m)<m(v). Then the periodic lower bound is (20). BA(w;m)+k+1≤m(w).B_A(w;m)+k+1\le m(w).(20)✦

What Is Checked

The preprocessing statement ranges over finite input lists and candidate superstrings. The recursion statements range over arbitrary finite count instances, and the periodic lower bound allows any positive period of an integer-indexed text.