Documentation

Bdd.Reduce.Process

structure Reduce.StepInv {n m : ℕ} (O : OBdd n m) (ps : ProvedState n m) (i s₀ : ℕ) (curkey : KeyPair) (curptr : RawBdd.RawPointer) (Q : List (KeyPair × Fin m)) :
Instances For

    The sentinel key (.terminal false, .terminal false) is the least key: .terminal false is the least RawPointer, so it is ≤ every key. Used as the initial curkey in step.

    theorem Reduce.sentinel_no_match {m : ℕ} (Q : List (KeyPair × Fin m)) (hnonred : ∀ entry ∈ Q, entry.1.1 ≠ entry.1.2) (entry : KeyPair × Fin m) :

    In a non-redundant queue, no entry's key matches the sentinel ⟨.terminal false, .terminal false⟩.

    def Reduce.process_queue {n m i : ℕ} (O : OBdd n m) (curkey : KeyPair) (curptr : RawBdd.RawPointer) (s₀ : ℕ) (Q : List (KeyPair × Fin m)) (ps : ProvedState n m) :
    Invariant O ps i → (∀ entry ∈ Q, RawBdd.RawPointer.Bounded ps.state.size entry.1.1 ∧ RawBdd.RawPointer.Bounded ps.state.size entry.1.2) → (hcurptr_sem : ∀ entry ∈ Q, entry.1 = curkey → ∃ (hj : { heap := O.bdd.heap, root := Pointer.node entry.2 }.Ordered) (hp : RawBdd.RawPointer.Bounded ps.state.size curptr) (ho : { heap := RawBdd.cook_heap ps.state.heap ⋯, root := curptr.cook hp }.Ordered), { bdd := { heap := RawBdd.cook_heap ps.state.heap ⋯, root := curptr.cook hp }, ordered := ho }.Reduced ∧ ∀ (I : Vector Bool n), { bdd := { heap := RawBdd.cook_heap ps.state.heap ⋯, root := curptr.cook hp }, ordered := ho }.evaluate I = { bdd := { heap := O.bdd.heap, root := Pointer.node entry.2 }, ordered := hj }.evaluate I) → (hec : ∀ entry ∈ Q, EntryCorrect O ps i entry) → (si : StepInv O ps i s₀ curkey curptr Q) → { ps' : ProvedState n m // Invariant O ps' i ∧ (∀ (k : Fin m), ps.state.ids[k].isSome = true → ps'.state.ids[k].isSome = true) ∧ (∀ entry ∈ Q, ps'.state.ids[entry.2].isSome = true) ∧ VarInvariant O ps' ∧ HeapInjective ps' ∧ ∀ (k : Fin ps'.state.size), i ≤ ↑ps'.state.heap[k].va }
    Equations
    Instances For