Documentation

Determinize.Proof.Frontend.Affinity

Correctness of the affinity solver #

The solutions of a list of affinity constraints are closed under pointwise join and meet (satisfies_join, satisfies_meet; Lemma L). solveAffinities succeeds exactly when there is a solution, and then returns one that lies above every solution (solveAffinities_spec; Lemma P).

ρ satisfies every constraint, in the order G ≤ E of Ty.Sub.

Equations
  • One or more equations did not get rendered due to their size.
Instances For

    Lemma L #

    theorem Determinize.Proof.Frontend.satisfies_join {V : Type} {ρ ρ' : V → Spec.Paper.Affinity} {constraints : List (Frontend.AffinityConstraint V)} (h : Satisfies ρ constraints) (h' : Satisfies ρ' constraints) :
    Satisfies (fun (v : V) => affinityJoin (ρ v) (ρ' v)) constraints
    theorem Determinize.Proof.Frontend.satisfies_meet {V : Type} {ρ ρ' : V → Spec.Paper.Affinity} {constraints : List (Frontend.AffinityConstraint V)} (h : Satisfies ρ constraints) (h' : Satisfies ρ' constraints) :
    Satisfies (fun (v : V) => affinityMeet (ρ v) (ρ' v)) constraints

    Lemma P #

    theorem Determinize.Proof.Frontend.mem_below {V : Type} [DecidableEq V] {constraints : List (Frontend.AffinityConstraint V)} {general : Finset V} {v : V} :
    v ∈ Frontend.below constraints general ↔ ∃ (upper : Frontend.AffinityTerm V), (Frontend.AffinityTerm.var v, upper) ∈ constraints ∧ Frontend.AffinityTerm.isGeneral general upper = true

    A solution is G on every term that isGeneral accepts, if it is G on general.

    theorem Determinize.Proof.Frontend.forcedGeneral_general {V : Type} [DecidableEq V] {ρ : V → Spec.Paper.Affinity} {constraints : List (Frontend.AffinityConstraint V)} (hρ : Satisfies ρ constraints) {general : Finset V} (h : ∀ v ∈ general, ρ v = Spec.Paper.Affinity.G) (v : V) :
    v ∈ Frontend.forcedGeneral constraints general → ρ v = Spec.Paper.Affinity.G

    Every solution is G on the variables that forcedGeneral collects.

    theorem Determinize.Proof.Frontend.below_forcedGeneral {V : Type} [DecidableEq V] (constraints : List (Frontend.AffinityConstraint V)) (general : Finset V) :
    Frontend.below constraints (Frontend.forcedGeneral constraints general) ⊆ Frontend.forcedGeneral constraints general

    The variables that forcedGeneral collects are closed under below.

    theorem Determinize.Proof.Frontend.solveAffinities_greatest {V : Type} [DecidableEq V] {constraints : List (Frontend.AffinityConstraint V)} {ρ ρ' : V → Spec.Paper.Affinity} (h : Frontend.solveAffinities constraints = some ρ) (h' : Satisfies ρ' constraints) (v : V) :

    The result of solveAffinities lies above every solution.

    theorem Determinize.Proof.Frontend.solveAffinities_spec {V : Type} [DecidableEq V] (constraints : List (Frontend.AffinityConstraint V)) :
    ((∃ (ρ : V → Spec.Paper.Affinity), Satisfies ρ constraints) ↔ ∃ (ρ : V → Spec.Paper.Affinity), Frontend.solveAffinities constraints = some ρ) ∧ ∀ (ρ : V → Spec.Paper.Affinity), Frontend.solveAffinities constraints = some ρ → Satisfies ρ constraints ∧ ∀ (ρ' : V → Spec.Paper.Affinity), Satisfies ρ' constraints → ∀ (v : V), (Spec.Paper.Ty.float (ρ' v)).Sub (Spec.Paper.Ty.float (ρ v))

    Lemma P: solveAffinities succeeds exactly when the constraints have a solution, and then returns a solution that lies above every solution.