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 be a finite job set, let be a precedence relation on , and let be rank functions. Write for the fixed leaf allowance.
A job triple is a set of cardinality three.✦ A scheduling boundary is a left endpoint , an actual job triple , or a right endpoint .✦ For a relation on , the strict predecessor and successor cones and , and their weak counterparts and , are the sets in (1). (1)
An orientation chooses a relation and a rank function: and , where means .
The Claim
Definition 1 (Boolean descriptions). An atomic structural predicate on is a symbol in the language of (2). For , the symbols and are upper and lower rank thresholds; for , the symbols select a boundary triple or one of its four cones. (2)✦
The interpretation assigns to each atom the job set specified in (3). (3)✦
A Boolean formula over an atomic alphabet is a finite expression built from positive leaves and negative leaves , for , by conjunction and disjunction.✦ Write for the set of these formulas. For Boolean formulas and an interpretation , the set interpretation of is the subset of defined by (4). (4)✦
The leaf count of a Boolean formula is the size measure in (5). (5)✦
Bounded Boolean describability of a set under an interpretation , with a nonnegative integer leaf budget , is the condition in (6). (6)✦
Relative Boolean describability of a set in a set , under an interpretation and with a nonnegative integer budget , is the condition in (7). (7)✦
The De Morgan negation of a Boolean formula is the formula obtained by toggling the sign of every leaf and exchanging conjunction with disjunction.✦
Theorem 1. Let be a Boolean formula over an atomic alphabet . Its De Morgan negation satisfies (8). (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.