Lemma 3.20 — Incompat(Δ) and ¬Elsewhere(Δ) are semantically equivalent
ProvedBiAbduction.Systematic.lemma_3_20abductionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1separation-logic
For every quantifier-free left-hand side of the Points-to Instantiation, the disjunction denotes exactly the incompatible solutions:
That is, a state satisfies iff no heap separate from its heap satisfies with the same stack.
This is the second phase of the systematic algorithm: the incompatible solutions are expressible as a disjunction of symbolic heaps.
Preamble
import Mathlib import Definitions.Def_BiAbduction_Systematic_Incompat
Formal statement
namespace BiAbduction.Systematic
/-- Lemma 3.20 (p. 32). `Incompat(Δ)` and `¬Elsewhere(Δ)` are semantically equivalent. -/
theorem lemma_3_20 (Δ : LHS) :
disjDen (incompat Δ) = (Elsewhere (lhsDen Δ))ᶜ := by sorry
end BiAbduction.Systematic
Source
Calcagno, Distefano, O'Hearn, Yang, Compositional Shape Analysis by means of Bi-Abduction, J. ACM (2011), p. 32, Lemma 3.20 (Incompat defined on p. 31)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.