Lemma 3.16 — min(D ∨ ¬Elsewhere(Δ)) is the ≾-minimal solution when D is ≤c-minimal
ProvedBiAbduction.Systematic.lemma_3_16abductionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1separation-logic
Let and be predicates and consider the abduction question . Let be a minimal solution w.r.t. the compatible preorder : , and for every predicate with . Then
is the minimal solution w.r.t. : it is a solution, and it is -below every solution (every predicate with ).
This lemma reduces the computation of the best solution to three phases: a -minimal solution, the incompatible solutions , and .
Formalization Note The page states the lemma for the symbolic heaps , of (5); its proof uses no syntax, and the statement here holds for arbitrary predicates , , , which includes the page's case.
Preamble
import Mathlib import Definitions.Def_BiAbduction_Systematic_Semantics
Formal statement
namespace BiAbduction.Systematic
/-- Lemma 3.16 (p. 27). If `D` is a minimal solution of `Δ ∗ ? ⊨ H` w.r.t. `≤c`, then
`min(D ∨ ¬Elsewhere(Δ))` is the minimal solution w.r.t. `≾`. -/
theorem lemma_3_16 (Δ H D : Pred) (hD : IsCompatMinSolution Δ H D) :
IsLeastSolution Δ H (minSet (D ∪ (Elsewhere Δ)ᶜ)) := by sorry
end BiAbduction.Systematic
Source
Calcagno, Distefano, O'Hearn, Yang, Compositional Shape Analysis by means of Bi-Abduction, J. ACM (2011), p. 27, Lemma 3.16
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.