The Setting
Let be a job set and a precedence relation, with meaning that must precede . A scheduling subproblem concerns an ambient set . The item defines recursive acceptance of these subproblems and the layers of a dynamic program that stores schedule blocks.
A job triple in is a finite subset with .✦ A schedule block on consists of a nonnegative length and a time assignment .✦ Write for the empty schedule block.
Boolean Descriptions
A Boolean structural formula over an atom set is a positive or negative atom, or a conjunction or disjunction of two formulas.✦ Fix an assignment . For formulas and over , the interpretation and leaf count are defined by (1), where complements are taken in : (1)
A job set has a bounded Boolean description with leaf allowance , written , when it satisfies (2): (2)✦ A relative Boolean description of a set inside , with leaf allowance , is a globally described subset of whose intersection with is ; write for its existence in (3): (3) The fixed allowance for structural acceptance is .
The Definition
Definition 1. Fix the precedence relation and the atom assignment. A structural split vertex of , with a job triple, is a partition satisfying (4); write for the set of these vertices: (4)✦
An admissible split transition relative to a property of job sets is an ordered pair of vertices and in satisfying (5): (5)✦ Write for a finite path of such transitions, including a path of length zero, and write for the left and right parts of a vertex .
A job set is structurally accepted at depth , written , when it satisfies (6): (6)✦
A scheduling state on is an ordered triple of finite job sets; write for the set of these states, as in (7), where denotes the collection of finite subsets of .
Equality of scheduling states is decidable. (7)✦
For lists and of finite job sets, and a list of pairs consisting of a finite job set and a schedule block, let denote the table of successful outputs obtained by solving each scheduling subproblem in using the schedule blocks in . The scheduling layers are lists of pairs consisting of a finite job set and a schedule block, defined by (8): (8)✦
In the paper, the result reads: compatible partitions have an antichain triple and a relative description of , initial and final states have accepted and , respectively, a transition requires and acceptance of , and a bounded-description hierarchy recursively marks at least one actual slot at every nonempty node after permitted interval reordering, takes its nonempty open gaps as children, globally describes each node, and relatively describes the jobs earlier than every mark in original time.
What Is Checked
The structural definitions are stated over a job set with a precedence relation and an assignment of job sets to atoms; the scheduling layers additionally take lists of candidate job sets and triples.