OctoInformBeta

OpenAI preprint, September 2026 · §5. Processing the period groups · §5

§5 (setting): finite layer collections, records and plans: Foreign interval records and outgoing plans with budgets for traversal and connection

Ordered periodic layers and their reserves.

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

Processing a periodic group concerns traversals of its actual layer windows. A connection to a recorded occurrence in a target layer has to fit within the traversal budget.

Let VV be a set of finite words over an alphabet α\alpha. For an integer-indexed text A:ℤ→αA\colon\mathbb Z\to\alpha and integers a,ba,b, the window A[a,b)A[a,b) is the finite word in (1); reversed endpoints give the empty word ε\varepsilon. A[a,b)={A(a)A(a+1)⋯A(b−1),a<b,ε,b≤a.A[a,b)= \begin{cases} A(a)A(a+1)\cdots A(b-1),&a<b,\\ \varepsilon,&b\le a. \end{cases}(1) Two texts AA and BB have interval agreement on [a,b)[a,b) when A(x)=B(x)A(x)=B(x) for every integer xx with a≤x<ba\le x<b.✦

A hierarchical walk in VV is a finite concatenation of up steps s→sas\to sa appending a symbol and down steps as→sas\to s deleting the first symbol, with both endpoints of every step in VV.✦ A stationary walk at a vertex of VV is allowed. A walk visits a word when that word is an actual vertex of the walk, including its endpoints.✦ Its cost is its number of up steps; stationary walks and down steps cost zero, and concatenation adds costs.✦ A loop is a hierarchical walk whose initial and final vertices coincide, with the same notions of visitation and cost.✦ For a hierarchical walk PP in VV, write Vis⁡(P)\operatorname{Vis}(P) for the set of words visited by PP.

A layer DD for a text AA and period parameter pp is a nondecreasing integer-valued exit function zDz_D satisfying (2). Here fDf_D and ℓD\ell_D are its first and last exit positions, and 𝒱(D)\mathcal V(D) is its content, the set of base layer vertices. fD(x)=zD(x−1),ℓD(x)=zD(x),x≤fD(x),zD(x+p)=zD(x)+p(x∈ℤ),𝒱(D)={A[x,e):x,e∈ℤ,fD(x)≤e≤ℓD(x)}⊆V.\begin{gathered} f_D(x)=z_D(x-1),\qquad \ell_D(x)=z_D(x),\\ x\le f_D(x),\qquad z_D(x+p)=z_D(x)+p\quad(x\in\mathbb Z),\\ \mathcal V(D)= \{A[x,e):x,e\in\mathbb Z,\ f_D(x)\le e\le\ell_D(x)\}\subseteq V. \end{gathered}(2)✦

A shifted record R=(δ,a,b)R=(\delta,a,b) of a text AA in a layer DD of text BB is a triple of integers satisfying (3). fD(a+δ)≤b+δ≤ℓD(a+δ),A(x)=B(x+δ)(a≤x<b).\begin{gathered} f_D(a+\delta)\le b+\delta\le\ell_D(a+\delta),\\ A(x)=B(x+\delta)\qquad(a\le x<b). \end{gathered}(3)✦

The Definition

Definition 1. An ordered layer collection CC on VV, indexed by a set GG of groups, consists of texts AgA_g, positive integers pg,ngp_g,n_g, and layers Dg,jD_{g,j} for AgA_g and pgp_g, where 0≤j<ng0\le j<n_g, satisfying (4). The chosen pgp_g is a period parameter. Ag(x+pg)=Ag(x)(g∈G,x∈ℤ),zDg,i(x)≤zDg,j(x)(0≤i≤j<ng,x∈ℤ),Ag≠Ah(⋅+c)(g≠h,c∈ℤ).\begin{gathered} A_g(x+p_g)=A_g(x)\qquad(g\in G,\ x\in\mathbb Z),\\ z_{D_{g,i}}(x)\le z_{D_{g,j}}(x) \qquad(0\le i\le j<n_g,\ x\in\mathbb Z),\\ A_g\ne A_h(\mathord\cdot+c) \qquad(g\ne h,\ c\in\mathbb Z). \end{gathered}(4)✦

The grouped layer index set is I={(g,j):g∈G,0≤j<ng}I=\{(g,j):g\in G,\ 0\le j<n_g\}✦; the indexed base layer at i=(g,j)i=(g,j) is Di=Dg,jD_i=D_{g,j}.✦

When α\alpha is linearly ordered, the forward rotation stream Fg(t)F_g(t) has the lexicographic order. A distinguished phase τg\tau_g selects a greatest rotation✦, and ρg\rho_g is the greatest rotation rank, as in (5). Fg(t)=(Ag(t+n))n≥0,Fg(t)≤lexFg(τg)(t∈ℤ),ρg=Fg(τg).F_g(t)=(A_g(t+n))_{n\ge0},\qquad F_g(t)\le_{\mathrm{lex}}F_g(\tau_g)\ (t\in\mathbb Z),\qquad \rho_g=F_g(\tau_g).(5)✦

For a group gg of an ordered layer collection CC, a threshold HH, an integer start tt and a nonnegative integer kk, the set Qg(t,H,k)Q_g(t,H,k) of qualifying layer indices is the set in (6). Qg(t,H,k)={j:0≤j<ng,H−kpg≤ℓDg,j(t)}.Q_g(t,H,k)=\{j:0\le j<n_g,\ H-kp_g\le\ell_{D_{g,j}}(t)\}.(6)✦

Definition 2. A collection CC has a foreign record supply if every group gg, layer Dg,jD_{g,j}, integer tt and positive integer kk satisfying t+kpg<fDg,j(t)t+kp_g<f_{D_{g,j}}(t) and |Qg(t,fDg,j(t),k)|≤k|Q_g(t,f_{D_{g,j}}(t),k)|\le k admit an index d=(h,r)∈Id=(h,r)\in I and a record R=(δ,a,b)R=(\delta,a,b) of AgA_g in DdD_d with the properties in (7). a≤t,fDg,j(t)−kpg≤b,Ag≠Ah(⋅+δ).a\le t,\qquad f_{D_{g,j}}(t)-kp_g\le b,\qquad A_g\ne A_h(\mathord\cdot+\delta).(7)✦

Definition 3. Assume that α\alpha is linearly ordered. An outgoing block plan Π\Pi for an ordered layer collection CC consists of a source group gg, a nonempty finite set M⊆IM\subseteq I consisting of indices of group gg, a target d=(h,r)∈Id=(h,r)\in I, and a record R=(δ,a,b)R=(\delta,a,b) of AgA_g in DdD_d such that Ag≠Ah(⋅+δ)A_g\ne A_h(\mathord\cdot+\delta). Put k=|M|k=|M|, 𝒱M=⋃i∈M𝒱(Di)\mathcal V_M=\bigcup_{i\in M}\mathcal V(D_i) and wR=Ag[a,b)w_R=A_g[a,b). The plan requires loops PℓP_{\ell} and P0P_0 satisfying the first two lines of (8). When ρh≤ρg\rho_h\le\rho_g, it also requires a loop PsP_s and a word vv satisfying its last line. cost⁡(Pℓ)≤2kpg,𝒱M∪{wR}⊆Vis⁡(Pℓ),cost⁡(P0)+pg≤2kpg,𝒱M⊆Vis⁡(P0),cost⁡(Ps)≤2kpg,𝒱M∪{wR,v}⊆Vis⁡(Ps),|v|≤ph.\begin{gathered} \operatorname{cost}(P_{\ell})\le2kp_g,\qquad \mathcal V_M\cup\{w_R\}\subseteq\operatorname{Vis}(P_{\ell}),\\ \operatorname{cost}(P_0)+p_g\le2kp_g,\qquad \mathcal V_M\subseteq\operatorname{Vis}(P_0),\\ \operatorname{cost}(P_s)\le2kp_g,\qquad \mathcal V_M\cup\{w_R,v\}\subseteq\operatorname{Vis}(P_s),\qquad |v|\le p_h. \end{gathered}(8)✦

What Is Checked

The collection definition (4) is stated over an arbitrary group index set, with finitely many layers in each group. The supply condition (7) ranges over integer positions and positive block lengths; the plan definition (8) additionally uses a linear order on the alphabet.

For a shifted record in (3), the source window A[a,b)A[a,b) equals the target window B[a+δ,b+δ)B[a+\delta,b+\delta) and belongs to the content of the target layer.