Theorem 3.13 — the unique ≾-minimal solution of F ∗ ? ⊨ G exists and is min(F −∗ G)
ProvedBiAbduction.Footprint.theorem_3_13abductionp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1separation-logic
Let be arbitrary predicates (sets of stack–heap pairs, heaps finite). The abduction question has a best solution with respect to the betterness order , namely
it is a solution, it satisfies for every solution (every predicate with ), and it is the only solution with this property.
This is the semantic answer to abduction against which the paper measures its algorithms, and Theorem 4.11 uses it to identify the anti-frames computed by an ideal bi-abductive prover.
Preamble
import Mathlib import Definitions.Def_BiAbduction_Footprint_Semantics
Formal statement
namespace BiAbduction.Footprint
/-- Theorem 3.13 (p. 24): the minimal solution of `F ∗ ? ⊨ G` w.r.t. `≾` always exists and is
`min(F −∗ G)`; it is the only `≾`-least solution. -/
theorem theorem_3_13 (F G : Pred) :
IsLeastSolution F G (minSet (wand F G)) ∧
∀ M : Pred, IsLeastSolution F G M → M = minSet (wand F G) := by sorry
end BiAbduction.Footprint
Source
Calcagno, Distefano, O'Hearn, Yang, Compositional Shape Analysis by means of Bi-Abduction, J. ACM (2011), p. 24, Theorem 3.13 (proof p. 25)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.