OctoInformBeta

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

§2 (setting): the hierarchical graph and base multiplicities: The graph data associated with forced occurrence counts

Hierarchical walks and base edge multiplicities.

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

The graph formulation of forced occurrence counts uses words as vertices. Its walks track changes to a current word, and its base edge multiplicities depend on counts of one-symbol extensions.

Let Σ\Sigma be a set of symbols, and let Σ*\Sigma^* be the set of finite words over Σ\Sigma. Write |s||s| for the symbol length of a word ss, and t≼st\preceq s when tt is a contiguous substring of ss, including the empty word. For a∈Σa\in\Sigma, the words asas and sasa prepend and append aa, respectively.

A finite count instance D=(VD,SD,AD)D=(V_D,S_D,A_D) consists of a finite set VD⊆Σ*V_D\subseteq \Sigma^* of substring vertices, a finite set SD⊆Σ*S_D\subseteq\Sigma^* of required input words, and a finite alphabet AD⊆ΣA_D\subseteq\Sigma.

The count iteration of DD is the sequence (mn)n≥0(m_n)_{n\geq0} of functions from words to nonnegative integers specified by (1), where FDF_D denotes the count recursion operator of DD. m0(s)=0,mn+1=FD(mn).m_0(s)=0, \qquad m_{n+1}=F_D(m_n).(1)✦ The maximum vertex length hDh_D of DD is the nonnegative integer specified by (2); it is zero when VDV_D is empty. The forced occurrence count mm of DD is the function from words to nonnegative integers specified by (2). hD=max⁡({0}∪{|s|:s∈VD}),m(s)=mhD+1(s).h_D=\max\bigl(\{0\}\cup\{|s|:s\in V_D\}\bigr), \qquad m(s)=m_{h_D+1}(s).(2)

The Definition

Definition 1 (Hierarchical graph and base multiplicities). A vertex set V⊆Σ*V\subseteq\Sigma^* is substring-closed when it satisfies (3). s∈V,t≼s⇒t∈V.s\in V,\quad t\preceq s \quad\Longrightarrow\quad t\in V.(3)✦ An up step goes from xx to xaxa, and a down step goes from axax to xx, for a symbol a∈Σa\in\Sigma, with both endpoints in VV. A hierarchical walk from ss to tt in VV is a finite vertex sequence in the set 𝒫V(s,t)\mathcal P_V(s,t) of (4). 𝒫V(s,t)={(v0,…,vk):k≥0,v0=s,vk=t,vi∈V(0≤i≤k),for each i<k there is a∈Σ such thatvi+1=via or vi=avi+1}.\begin{split} \mathcal P_V(s,t)=\bigl\{(v_0,\ldots,v_k):\;& k\geq0,\quad v_0=s,\quad v_k=t,\\ &v_i\in V\quad(0\leq i\leq k),\\ &\text{for each }i<k\text{ there is }a\in\Sigma\text{ such that}\\ &v_{i+1}=v_i a\ \text{ or }\ v_i=a v_{i+1}\bigr\}. \end{split}(4)✦ Write 1s1_s for the walk with no steps at s∈Vs\in V, and PQPQ for the concatenation of walks PP and QQ with matching endpoints. The cost c(P)c(P) of a hierarchical walk PP is the nonnegative integer defined by (5). c(1s)=0,c(x→xa)=1,c(ax→x)=0,c(PQ)=c(P)+c(Q).\begin{aligned} c(1_s)&=0, & c(x\to xa)&=1,\\ c(ax\to x)&=0, & c(PQ)&=c(P)+c(Q). \end{aligned}(5)✦ For a finite count instance DD and a word s∈Σ*s\in\Sigma^*, the base upward edge multiplicity u(s)u(s) is the nonnegative integer in (6). u(s)=max⁡{m(s)−∑a∈ADm(as),0}.u(s)=\max\left\{m(s)-\sum_{a\in A_D}m(as),\,0\right\}.(6)✦ The base downward edge multiplicity d(s)d(s) of a word s∈Σ*s\in\Sigma^* is the nonnegative integer in (7). d(s)=max⁡{m(s)−∑a∈ADm(sa),0}.d(s)=\max\left\{m(s)-\sum_{a\in A_D}m(sa),\,0\right\}.(7)✦

What Is Checked

The definitions are stated over arbitrary sets of word vertices and finite count instances over a common symbol set.