Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 4.11 (Deriving Footprint) — with precise preconditions and best anti-frames, foot(C) = P_C

Proved
BiAbduction.Footprint.theorem_4_11

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

abductionfootprintp2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1program-analysisseparation-logic

Let C=α;C′C = \alpha; C'C=α;C′ be a nonempty sequence of actions, each action β\betaβ given by its specification {Pβ} β {Qβ}\{P_\beta\}\,\beta\,\{Q_\beta\}{Pβ​}β{Qβ​}, and suppose that every precondition PβP_\betaPβ​ of the sequence is precise. Let PCP_CPC​ be the precondition of the canonical spec of CCC obtained when every call to the bi-abductive prover delivers the best anti-frame: PαP_\alphaPα​ for a single action, and Pα∗MP_\alpha * MPα​∗M for α;C′\alpha; C'α;C′, where MMM is the best solution of Qα∗M⊨PC′∗trueQ_\alpha * M \models P_{C'} * \mathsf{true}Qα​∗M⊨PC′​∗true. Then

foot(C)=PC,\mathrm{foot}(C) = P_C,foot(C)=PC​,

an equality of predicates, where foot(C)=min⁡(safe(C))\mathrm{foot}(C) = \min(\mathrm{safe}(C))foot(C)=min(safe(C)) is the footprint of Definition 4.10.

The theorem says that, on straight-line paths, analysis by bi-abduction with an ideal prover infers exactly the footprint: the minimal states on which the sequence does not fault.

Formalization Note A sequence is a head action and a tail list. The canonical precondition is the inductive relation IsCanonPre, built from the proof of the theorem (the paper does not define the canonical spec in §4.2.4); its anti-frames are arbitrary ≾-least solutions, so the theorem is not an unfolding of a definition. Precision is assumed for every action of the sequence, including the last.

Preamble
import Mathlib
import Definitions.Def_BiAbduction_Footprint_Semantics
import Definitions.Def_BiAbduction_Footprint_Footprint
Formal statement
namespace BiAbduction.Footprint

/-- Theorem 4.11 (Deriving Footprint, p. 50): if the precondition of every action of the sequence
`α; C` is precise and `P` is the precondition of the canonical spec of `α; C` obtained when
every bi-abduction call delivers the best anti-frame, then `foot(α; C) = P`. -/
theorem theorem_4_11 (α : Action) (C : List Action) (P : Pred)
    (hprec : ∀ a ∈ α :: C, IsPrecise a.pre) (hcanon : IsCanonPre α C P) :
    foot α C = P := by sorry

end BiAbduction.Footprint
Source
Calcagno, Distefano, O'Hearn, Yang, Compositional Shape Analysis by means of Bi-Abduction, J. ACM (2011), p. 50, Theorem 4.11
Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 7, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me