OctoInformBeta

OpenAI preprint, September 2026 · §2. Full schedules, frames, and descriptions

§2 (setting): the fixed family of Boolean descriptions: A fixed atomic language with leaf budgets for global and relative descriptions

Boolean formulas describe sets of jobs.

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

Which job sets can be selected by rank tests and precedence conditions at boundary triples when the selecting expression has a fixed size budget? Let JJ be a finite job set, let rr be a precedence relation on JJ, and let ρ,ρrev:J→ℕ\rho,\rho_{\mathrm{rev}}:J\to \mathbb N be rank functions. Write K=10000K=10000 for the fixed leaf allowance.

A job triple Z⊆JZ\subseteq J is a set of cardinality three.✦ A scheduling boundary BB is a left endpoint ⊥\bot, an actual job triple ZZ, or a right endpoint ⊤\top.✦ For a relation RR on JJ, the strict predecessor and successor cones PR(B)P_R(B) and DR(B)D_R(B), and their weak counterparts PRw(B)P_R^{\mathrm w}(B) and DRw(B)D_R^{\mathrm w}(B), are the sets in (1). B⊥Z⊤PR(B)⌀{x∈J:∃y∈Z,xRy}JDR(B)J{x∈J:∃y∈Z,yRx}⌀PRw(B)⌀PR(Z)∪ZJDRw(B)JDR(Z)∪Z⌀\begin{array}{c|ccc} B & \bot & Z & \top \\ \hline P_R(B) & \varnothing & \{x\in J:\exists y\in Z,\ xRy\} & J \\ D_R(B) & J & \{x\in J:\exists y\in Z,\ yRx\} & \varnothing \\ P_R^{\mathrm w}(B) & \varnothing & P_R(Z)\cup Z & J \\ D_R^{\mathrm w}(B) & J & D_R(Z)\cup Z & \varnothing \end{array}(1)

An orientation ε∈{0,1}\varepsilon\in\{0,1\} chooses a relation and a rank function: (R0,σ0)=(r,ρ)(R_0,\sigma_0)=(r,\rho) and (R1,σ1)=(rop,ρrev)(R_1,\sigma_1)=(r^{\mathrm{op}},\rho_{\mathrm{rev}}), where xropyx\,r^{\mathrm{op}}\,y means yrxy\,r\,x.

The Claim

Definition 1 (Boolean descriptions). An atomic structural predicate aa on JJ is a symbol in the language 𝒜J\mathcal A_J of (2). For t∈{0,…,|J|+1}t\in\{0,\ldots,|J|+1\}, the symbols Uε,tU_{\varepsilon,t} and Lε,tL_{\varepsilon,t} are upper and lower rank thresholds; for h∈{0,…,4}h\in\{0,\ldots,4\}, the symbols Cε,h,ZC_{\varepsilon,h,Z} select a boundary triple or one of its four cones. 𝒜J={𝟎,𝟏}∪{Uε,t,Lε,t:ε∈{0,1},t∈{0,…,|J|+1}}∪{Cε,h,Z:ε∈{0,1},h∈{0,…,4},Z⊆J,|Z|=3}.\begin{aligned} \mathcal A_J={}&\{\mathbf 0,\mathbf 1\}\\ &{}\cup\{U_{\varepsilon,t},L_{\varepsilon,t}: \varepsilon\in\{0,1\},\ t\in\{0,\ldots,|J|+1\}\}\\ &{}\cup\{C_{\varepsilon,h,Z}: \varepsilon\in\{0,1\},\ h\in\{0,\ldots,4\},\ Z\subseteq J,\ |Z|=3\}. \end{aligned}(2)✦

The interpretation ℐJ:𝒜J→2J\mathcal I_J:\mathcal A_J\to 2^J assigns to each atom the job set specified in (3). ℐJ(𝟎)=⌀,ℐJ(𝟏)=J,ℐJ(Uε,t)={x∈J:σε(x)≤t},ℐJ(Lε,t)={x∈J:t≤σε(x)},ℐJ(Cε,h,Z)={Z,h=0,PRε(Z),h=1,DRε(Z),h=2,PRεw(Z),h=3,DRεw(Z),h=4.\begin{aligned} \mathcal I_J(\mathbf 0)&=\varnothing, &\mathcal I_J(\mathbf 1)&=J,\\ \mathcal I_J(U_{\varepsilon,t})&=\{x\in J:\sigma_\varepsilon(x)\le t\}, &\mathcal I_J(L_{\varepsilon,t})&=\{x\in J:t\le\sigma_\varepsilon(x)\},\\ \mathcal I_J(C_{\varepsilon,h,Z}) &=\begin{cases} Z,&h=0,\\ P_{R_\varepsilon}(Z),&h=1,\\ D_{R_\varepsilon}(Z),&h=2,\\ P_{R_\varepsilon}^{\mathrm w}(Z),&h=3,\\ D_{R_\varepsilon}^{\mathrm w}(Z),&h=4. \end{cases} \end{aligned}(3)✦

A Boolean formula pp over an atomic alphabet AA is a finite expression built from positive leaves aa and negative leaves ¬a\neg a, for a∈Aa\in A, by conjunction and disjunction.✦ Write ℱA\mathcal F_A for the set of these formulas. For Boolean formulas p,q∈ℱAp,q\in\mathcal F_A and an interpretation ℐ:A→2J\mathcal I:A\to 2^J, the set interpretation Eℐ(p)E_{\mathcal I}(p) of pp is the subset of JJ defined by (4). Eℐ(a)=ℐ(a),Eℐ(¬a)=J\ℐ(a),Eℐ(p∧q)=Eℐ(p)∩Eℐ(q),Eℐ(p∨q)=Eℐ(p)∪Eℐ(q).\begin{aligned} E_{\mathcal I}(a)&=\mathcal I(a), &E_{\mathcal I}(\neg a)&=J\setminus\mathcal I(a),\\ E_{\mathcal I}(p\wedge q)&=E_{\mathcal I}(p)\cap E_{\mathcal I}(q), &E_{\mathcal I}(p\vee q)&=E_{\mathcal I}(p)\cup E_{\mathcal I}(q). \end{aligned}(4)✦

The leaf count ℓ(p)\ell(p) of a Boolean formula pp is the size measure in (5). ℓ(a)=ℓ(¬a)=1,ℓ(p∧q)=ℓ(p)+ℓ(q),ℓ(p∨q)=ℓ(p)+ℓ(q).\begin{aligned} \ell(a)&=\ell(\neg a)=1,\\ \ell(p\wedge q)&=\ell(p)+\ell(q), &\ell(p\vee q)&=\ell(p)+\ell(q). \end{aligned}(5)✦

Bounded Boolean describability Desc⁡ℐ(F,k)\operatorname{Desc}_{\mathcal I}(F,k) of a set F⊆JF\subseteq J under an interpretation ℐ:A→2J\mathcal I:A\to 2^J, with a nonnegative integer leaf budget kk, is the condition in (6). Desc⁡ℐ(F,k)⇔∃p∈ℱA:Eℐ(p)=F and ℓ(p)≤k.\operatorname{Desc}_{\mathcal I}(F,k) \quad\Longleftrightarrow\quad \exists p\in\mathcal F_A: \ E_{\mathcal I}(p)=F\ \text{ and }\ \ell(p)\le k.(6)✦

Relative Boolean describability RelDesc⁡ℐ(W,L,k)\operatorname{RelDesc}_{\mathcal I}(W,L,k) of a set L⊆JL\subseteq J in a set W⊆JW\subseteq J, under an interpretation ℐ:A→2J\mathcal I:A\to 2^J and with a nonnegative integer budget kk, is the condition in (7). RelDesc⁡ℐ(W,L,k)⇔∃F⊆J:Desc⁡ℐ(F,k) and L=W∩F.\operatorname{RelDesc}_{\mathcal I}(W,L,k) \quad\Longleftrightarrow\quad \exists F\subseteq J:\ \operatorname{Desc}_{\mathcal I}(F,k)\ \text{ and }\ L=W\cap F.(7)✦

The De Morgan negation p†p^\dagger of a Boolean formula pp is the formula obtained by toggling the sign of every leaf and exchanging conjunction with disjunction.✦

Theorem 1. Let pp be a Boolean formula over an atomic alphabet AA. Its De Morgan negation satisfies (8). ℓ(p†)=ℓ(p).\ell(p^\dagger)=\ell(p).(8)✦

What Is Checked

The atomic interpretation is stated over a finite job set, a precedence relation, and two rank functions; bounded and relative descriptions are stated over any atomic alphabet interpreted as subsets of a job set.