OctoInformBeta

OpenAI preprint, September 2026 · §8. Global interval predicates and completion

Lemma 8.2: Boundary prefixes and time-induced split vertices supply the local constructions for reversal of precedence

Certified edge prefixes have bounded descriptions.

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 cut through a full three-machine schedule separates the jobs before its boundary triple from those after it. The issue is the size of a Boolean description of these regions inside a parent window. The library states a bound for the target of an edge structural certificate, together with constructions of split vertices and their reversals.

Let TT be a valid deadline and JJ a finite job set of size N=3TN=3T, with precedence relation rr and rank ρ:J→ℕ\rho:J\to\mathbb N. A layout pp is a bijection from JJ to the positions 0,…,N−10,\ldots,N-1, read in consecutive triples.✦ Its slot assignment and the condition for a full precedence-respecting layout are given by (1). tp(x)=⌊p(x)3⌋+1,r(x,y)⇒tp(x)<tp(y).t_p(x)=\left\lfloor\frac{p(x)}3\right\rfloor+1, \qquad r(x,y)\Longrightarrow t_p(x)<t_p(y).(1) For boundary slots aa and bb, the open scheduling window W=(a,b)W=(a,b) is the job set in (2). W=(a,b)={x∈J:a<tp(x)<b}.W=(a,b)=\{x\in J:a<t_p(x)<b\}.(2)✦ Times and ranks refer to the working frame, which may reverse original precedence and time. The ranks in opposite frames sum to N+1N+1.

Boundaries and Boolean Descriptions

A job triple Z⊆JZ\subseteq J is a set of three jobs.✦ A scheduling triple boundary BB of a layout pp is an actual triple or one of the endpoints ⊥,⊤\bot,\top.✦ The boundary time of a scheduling triple boundary BB of a layout pp is 00 at ⊥\bot and T+1T+1 at ⊤\top; for an actual triple ZZ, the boundary time is ss when 1≤s≤T1\leq s\leq T and Z={x:tp(x)=s}Z=\{x:t_p(x)=s\}.✦

The strict predecessor and successor cones of an actual triple, and their weak versions, are the sets in (3). At ⊥\bot both predecessor cones are empty and both successor cones are JJ; at ⊤\top these assignments are reversed. P(Z)={x:∃z∈Z,r(x,z)},D(Z)={x:∃z∈Z,r(z,x)},Pw(Z)=P(Z)∪Z,Dw(Z)=D(Z)∪Z.\begin{aligned} P(Z)&=\{x:\exists z\in Z,\ r(x,z)\},& D(Z)&=\{x:\exists z\in Z,\ r(z,x)\},\\ P^{\mathrm w}(Z)&=P(Z)\cup Z,& D^{\mathrm w}(Z)&=D(Z)\cup Z. \end{aligned}(3) For a boundary BB and a job set HH, the boundary prefix set βB(H)\beta_B(H) is defined by (4). βB(H)=P(B)∪(H\Dw(B)).\beta_B(H)=P(B)\cup\bigl(H\setminus D^{\mathrm w}(B)\bigr).(4)✦ A boundary BB separates a job set XX at slot ss using a cutoff CC when every x∈Xx\in X earlier than ss and outside CC belongs to P(B)P(B), and every x∈Xx\in X later than ss and inside CC belongs to D(B)D(B).✦

An atomic family 𝒜=(Aα)\mathcal A=(A_\alpha) on JJ is an indexed family of subsets of JJ, with one subset assigned to each atom. A Boolean structural formula ff over an atomic family 𝒜\mathcal A is a signed atom or a conjunction or disjunction of two such formulas.✦ The job set denoted by a Boolean structural formula ff over 𝒜\mathcal A is written ⟦f⟧𝒜\llbracket f\rrbracket_{\mathcal A}: a positive atom denotes AαA_\alpha and a negative atom its complement in JJ, while conjunction and disjunction denote intersection and union.✦ The leaf count ℓ(f)\ell(f) of a Boolean structural formula ff is one at an atom and the sum of the two counts at either binary operation.✦ For a leaf bound kk, the collection 𝒟k\mathcal D_k of globally described subsets of JJ and the collection ℛk(W)\mathcal R_k(W) of subsets with a relative description in WW are defined by (5). 𝒟k={⟦f⟧𝒜:ℓ(f)≤k},ℛk(W)={W∩F:F∈𝒟k}.\mathcal D_k=\{\llbracket f\rrbracket_{\mathcal A}:\ell(f)\leq k\}, \qquad \mathcal R_k(W)=\{W\cap F:F\in\mathcal D_k\}.(5) The rank upper tail {x:h≤ρ(x)}\{x:h\leq\rho(x)\} at threshold hh for the rank ρ\rho on JJ is the set of jobs whose ranks are at least hh.✦ An expressive atomic family 𝒜\mathcal A for the precedence relation rr and rank ρ\rho on JJ is an atomic family for which JJ, the empty set, every rank upper tail, every triple, and all four cones of every boundary belong to 𝒟1\mathcal D_1.✦

A scheduling split vertex of WW is a partition (L,Z,R)(L,Z,R) of WW into pairwise disjoint regions, where ZZ is a triple that is an antichain for rr. No precedence edge goes from ZZ to LL, from RR to LL, or from RR to ZZ, and L,R∈ℛK(W)L,R\in\mathcal R_K(W), with the fixed allowance K=10000K=10000. Write 𝒮(r,𝒜,W)\mathscr S(r,\mathcal A,W) for the set of these vertices.

Edge Certificates

An indexed global set family ℰ=(Ei)i∈ℕ\mathcal E=(E_i)_{i\in\mathbb N} on JJ is a sequence of subsets of JJ with a finite set I⊆ℕI\subseteq\mathbb N of listed indices.✦ The entry union QQ of an indexed global set family ℰ=(Ei)i∈ℕ\mathcal E=(E_i)_{i\in\mathbb N} with listed indices II is the job set given by Q=⋃i∈IEiQ=\bigcup_{i\in I}E_i.✦ The membership indices of a job x∈Jx\in J are the indices in II whose entries in ℰ=(Ei)i∈ℕ\mathcal E=(E_i)_{i\in\mathbb N} contain xx; the last membership index m(x)m(x) is the maximum membership index of xx, with default zero. Lexicographic list priority orders jobs by (m(x),ρ(x))(m(x),\rho(x)).✦ A set UU is upward closed when x∈Ux\in U and r(x,y)r(x,y) imply y∈Uy\in U.✦ The family ℰ=(Ei)i∈ℕ\mathcal E=(E_i)_{i\in\mathbb N} with listed indices II has upward closed entries when every EiE_i with i∈Ii\in I is upward closed.✦ The injection entries of ℰ=(Ei)i∈ℕ\mathcal E=(E_i)_{i\in\mathbb N} with listed indices II are disjoint in WW when the sets W∩EiW\cap E_i, for listed i≥2i\geq2, are pairwise disjoint.✦

A rank threshold run certificate for ℰ\mathcal E in WW consists of bases UiU_i, thresholds hih_i, and a second set S1S_1, subject to (6). Ei=Ui∩{x:hi≤ρ(x)}(i∈I),Ui∈𝒟2(i∈I,i≠0),U0∈𝒟24,U1=S1∈𝒟1,W\S1⊆U0,0∈I⇒(∀x∈W∩S1,1∈Iandx∈E1).\begin{aligned} E_i&=U_i\cap\{x:h_i\leq\rho(x)\} &&(i\in I),\\ U_i&\in\mathcal D_2 &&(i\in I,\ i\ne0),\\ U_0&\in\mathcal D_{24},\qquad U_1=S_1\in\mathcal D_1, &W\setminus S_1&\subseteq U_0,\\ 0\in I&\Longrightarrow \bigl(\forall x\in W\cap S_1,\ 1\in I\ \text{and}\ x\in E_1\bigr). \end{aligned}(6)✦ For a boundary A′A' at slot a′a', the past boundary invariant requires every x∈Qx\in Q with tp(x)≤a′t_p(x)\leq a' to belong to Pw(A′)P^{\mathrm w}(A').✦

A layout qq is unchanged outside a job set XX relative to pp when q(x)=p(x)q(x)=p(x) for every x∉Xx\notin X.✦ Exchanging two jobs trades their positions and leaves all other positions fixed.✦ The forbidden exchange invariant on XX at A′,a′A',a' requires the following condition for every precedence-respecting layout qq unchanged outside XX: if x∈X\D(A′)x\in X\setminus D(A'), y∈Qy\in Q has tq(y)=a′t_q(y)=a', and xx has list priority over yy, then exchanging x,yx,y violates precedence feasibility.✦

An edge structural certificate uses a full layout pp, the parent W=(a,b)W=(a,b), and boundaries B,V,A′,B′B,V,A',B' at slots b,v,a′,b′b,v,a',b', respectively, with B′B' actual and the slot conditions in (7). a≤a′<b′≤v<b.a\leq a'<b'\leq v<b.(7) Its cutoff CC and final cutoff S∈𝒟1S\in\mathcal D_1 satisfy W∩C⊆P(B)∩SW\cap C\subseteq P(B)\cap S. The boundary VV separates WW at vv using SS; the boundaries A′A' and B′B' separate (a,v)(a,v) at a′a' and b′b' using CC. Its global family has a rank threshold run certificate, upward closed entries and second set, disjoint injection entries in WW, and W∩Q=W\CW\cap Q=W\setminus C. It satisfies the past boundary invariant at A′,a′A',a' and the forbidden exchange invariant on (a′,b′)(a',b') at A′,a′A',a'. A global cutoff G∈𝒟205G\in\mathcal D_{205} and a downward closed lower extension H∈𝒟21H\in\mathcal D_{21} both agree with CC inside WW; downward closure means that every predecessor of a job in HH belongs to HH.

The Claim

Theorem 1. For an expressive atomic family, any boundary BB and any H∈𝒟kH\in\mathcal D_k satisfy the boundary prefix bound βB(H)∈𝒟k+2.\beta_B(H)\in\mathcal D_{k+2}.(8)✦ Let an edge structural certificate be given for an expressive atomic family, with its one-leaf final cutoff. There is a global job set FF such that F∈𝒟210,W∩F={x∈W:tp(x)<b′}.F\in\mathcal D_{210},\qquad W\cap F=\{x\in W:t_p(x)<b'\}.(9)✦ Let pp be full, W=(a,b)W=(a,b), and a<s<ba<s<b. Suppose the actual boundary triple ZZ is at slot ss, F∈𝒟kF\in\mathcal D_k, k+1≤Kk+1\leq K, Z∈𝒟1Z\in\mathcal D_1, and W∩F={x∈W:tp(x)<s}W\cap F=\{x\in W:t_p(x)<s\}. The time-induced split vertex Split⁡s(p,Z,F)\operatorname{Split}_s(p,Z,F) has as its left region the jobs of WW before slot ss, as its middle triple ZZ, and as its right region the jobs of WW after slot ss. Split⁡s(p,Z,F)∈𝒮(r,𝒜,W).\operatorname{Split}_s(p,Z,F)\in\mathscr S(r,\mathcal A,W).(10)✦ For any split vertex (L,Z,R)∈𝒮(r,𝒜,W)(L,Z,R)\in\mathscr S(r,\mathcal A,W), reversing the precedence relation gives the reversed split vertex (R,Z,L)∈𝒮(rop,𝒜,W),rop(x,y)=r(y,x).(R,Z,L)\in\mathscr S(r^{\mathrm{op}},\mathcal A,W), \qquad r^{\mathrm{op}}(x,y)=r(y,x).(11)✦

In the paper, the result reads: every marked slot zz in a node WW has a relative description of its earlier jobs in its producing working direction and in original time, in the permitted atomic language and with fewer than 500500 leaves.

What Is Checked

The bounds (8) and (9) are stated over finite job sets, precedence relations and ranks with expressive atomic families, using boundary prefix sets and edge structural certificates, respectively; the constructions (10) and (11) concern full layouts with the stated interior boundary and description hypotheses, and arbitrary scheduling split vertices, respectively.