Pith. sign in

REVIEW 2 major objections 3 minor 12 references

Combining Axiomatic Models for Refinement Proofs

T0 review · 2 major / 3 minor · reviewed 2026-06-29 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read A relation is a simulation exactly when specific triples hold in one of four program logics.

desk verdict The paper reduces simulation checks to triple validity in Hoare/Lisbon/NP/Incorrectness logics using a uniform classification by direction and approximation. read the letter →

arxiv 2606.27916 v1 pith:T6MMWIRT submitted 2026-06-26 cs.LO

Suha Orhun Mutluergil , Alperen Dogan This is my paper · ORCID
classification cs.LO
keywords simulationrelationsrefinementproofsHoarelogicIncorrectnessprogramlogicsconcurrentprogramsaxiomaticsemantics
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Refinement proofs establish that every behavior of an implementation is already allowed by a simpler specification. The paper gives a uniform classification of Hoare logic, Incorrectness logic, Lisbon logic, and Necessary-Preconditions logic according to the direction in which each constrains a transition and whether it over- or under-approximates its target set. It shows that forward simulations carry Hoare invariants from specification to implementation while both forward and backward simulations carry ordinary invariants via the pre-image of the relation. The central result is that a relation is a forward simulation precisely when certain Hoare or Lisbon triples are valid and a backward simulation when Necessary-Preconditions or Incorrectness triples are valid, so that checking the simulation reduces to a standard triple in an existing logic. The development is illustrated by transporting a safety bound across forward and backward simulations in a concurrent counter example.

What carries the argument

The uniform classification of the four logics by transition direction and over- or under-approximation, used to reduce simulation checks to triple validity.

What would settle it

A concrete relation and pair of programs where the relevant triples are valid yet the relation fails to be a simulation (or vice versa) according to the standard relational definition.

Watch

Extended reading notes

Core claim

We characterize, within these logics, when a relation is a simulation: forward simulations by the validity of Hoare or Lisbon triples, backward simulations by Necessary-Preconditions or Incorrectness triples, so that the simulation obligation reduces to a triple in an off-the-shelf functional logic.

Load-bearing premise

The uniform classification of the four logics by direction and approximation is sound and complete for transferring invariants via simulations.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper gives a uniform semantic classification of Hoare, Incorrectness, Lisbon and Necessary-Preconditions logics according to transition direction and over-/under-approximation. It proves that forward simulations transport Hoare invariants while both forward and backward simulations transport ordinary invariants via the pre-image of the relation. It then shows that a relation is a forward simulation precisely when certain Hoare or Lisbon triples are valid, and a backward simulation precisely when certain Necessary-Preconditions or Incorrectness triples are valid, thereby reducing simulation obligations to checks inside the four logics. The claims are illustrated by transporting a safety bound across a forward simulation followed by a backward simulation in a concurrent-counter refinement chain.

Significance. If the stated equivalences hold, the work supplies a practical bridge between relational refinement and off-the-shelf axiomatic verification: simulation obligations become ordinary triple validity checks. The uniform classification and the two invariant-transfer theorems are the central contributions; the concurrent-counter example demonstrates their use on a non-trivial refinement that mixes forward and backward steps. No machine-checked proofs or parameter-free derivations are claimed.

major comments (2)
  1. [§4.1, Theorem 4.3] §4.1, Theorem 4.3 (backward-simulation transfer): the argument that an ordinary invariant is preserved under the pre-image relies on the simulation being a total relation on the reachable states of the implementation; this totality assumption is used without being stated in the theorem statement and is not discharged in the concurrent-counter example of §6.
  2. [§5.2] §5.2, equivalence for Lisbon triples: the direction of the implication 'Lisbon triple valid ⇒ forward simulation' is shown only for postconditions that are inductive invariants of the specification; the converse direction (simulation ⇒ triple) holds unconditionally, so the claimed 'if and only if' characterisation is one-sided for Lisbon logic and should be stated as such.
minor comments (3)
  1. A single table collecting the four logics, their direction, approximation type and the corresponding simulation characterisation would improve readability.
  2. [§4] Notation for the 'pre-image' operator is introduced in §4 but used without re-statement in the proof of Theorem 5.1; a local reminder would help.
  3. [Abstract] The abstract refers to 'Lisbon' logic without a one-sentence gloss; readers outside the immediate sub-area would benefit from a parenthetical.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on the manuscript. We address each major comment below.

read point-by-point responses

  1. Referee: [§4.1, Theorem 4.3] §4.1, Theorem 4.3 (backward-simulation transfer): the argument that an ordinary invariant is preserved under the pre-image relies on the simulation being a total relation on the reachable states of the implementation; this totality assumption is used without being stated in the theorem statement and is not discharged in the concurrent-counter example of §6.

    Authors: We agree that the totality assumption on reachable states is implicit in the proof of Theorem 4.3 but not stated in the theorem itself. We will revise the theorem statement to make this assumption explicit. We will also verify the assumption in the concurrent-counter example of §6 and add a brief discharge or note if it holds under the given reachability conditions. revision: yes

  2. Referee: [§5.2] §5.2, equivalence for Lisbon triples: the direction of the implication 'Lisbon triple valid ⇒ forward simulation' is shown only for postconditions that are inductive invariants of the specification; the converse direction (simulation ⇒ triple) holds unconditionally, so the claimed 'if and only if' characterisation is one-sided for Lisbon logic and should be stated as such.

    Authors: We acknowledge the observation. The manuscript claims an 'if and only if' for Lisbon triples in §5.2, but the 'valid triple ⇒ simulation' direction requires the postcondition to be an inductive invariant. We will revise the text to state the characterization precisely, noting the additional condition for one direction. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity

full rationale

The paper's central results consist of a uniform semantic classification of four standard program logics by transition direction and over-/under-approximation, followed by preservation theorems for invariants under forward and backward simulations, and equivalences showing that simulation relations correspond to validity of specific triples (Hoare/Lisbon or NP/Incorrectness). These are derived directly from the definitions of the logics and the simulation relations themselves, with no reduction to fitted parameters, self-referential definitions, or load-bearing self-citations. The concurrent-counter example merely illustrates the transfer argument. The development is therefore self-contained against external benchmarks in program verification.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

Abstract provides no information on free parameters, background axioms, or invented entities; all such details would require the full text.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Combining Axiomatic Models for Refinement Proofs." pith.science (2026). https://pith.science/paper/T6MMWIRT

@misc{pith2026260627916,
  author       = {Pith},
  title        = {Pith review of: Combining Axiomatic Models for Refinement Proofs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/T6MMWIRT}},
  note         = {Machine review of arXiv:2606.27916}
}
read the original abstract

Refinement proofs verify an implementation by showing that its behaviours are subsumed by a simpler specification, on which safety properties are easier to establish. We study how such proofs interact with the axiomatic program logics used to verify the specification. We first give a uniform account of Hoare, Incorrectness, Lisbon, and Necessary-Preconditions logic, classified by the direction in which each constrains a transition and by whether it over- or under-approximates its target set. We then show that simulation relations transfer state-based safety properties: a forward simulation carries a Hoare (inductive) invariant of the specification to one of the implementations, and forward and backward simulations both carry ordinary invariants, via the pre-image of the relation. Finally, we characterize, within these logics, when a relation is a simulation, forward simulations by the validity of Hoare or Lisbon triples, backward simulations by Necessary-Preconditions or Incorrectness triples, so that the simulation obligation reduces to a triple in an off-the-shelf functional logic. We illustrate the development with a concurrent counter, transporting a safety bound from an atomic sequential specification to a Left--Right implementation through an intermediate nondeterministic-concurrent counter, with a forward simulation on one side and a backward simulation on the other.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 5 canonical work pages

  1. [1]

    CoRR , volume =

    Shushu WU and Xiwei WU and Qinxiang Cao , title =. CoRR , volume =. 2025 , url =. doi:10.48550/ARXIV.2504.17444 , eprinttype =. 2504.17444 , timestamp =

    work page doi:10.48550/arxiv.2504.17444 2025

  2. [2]

    Lynch and Frits W

    Nancy A. Lynch and Frits W. Vaandrager , title =. Inf. Comput. , volume =. 1995 , url =. doi:10.1006/INCO.1995.1134 , timestamp =

    work page doi:10.1006/inco.1995.1134 1995

  3. [3]

    Sufficient incorrectness logic: SIL and separation SIL.CoRR, abs/2310.18156,

    Flavio Ascari and Roberto Bruni and Roberta Gori and Francesco Logozzo , title =. CoRR , volume =. 2023 , url =. doi:10.48550/ARXIV.2310.18156 , eprinttype =. 2310.18156 , timestamp =

    work page doi:10.48550/arxiv.2310.18156 2023

  4. [4]

    Lena Verscht and Benjamin Lucien Kaminski , title =. Proc. 2025 , url =. doi:10.1145/3704896 , timestamp =

    work page doi:10.1145/3704896 2025

  5. [5]

    Acta Informatica , volume =

    Susan Owicki and David Gries , title =. Acta Informatica , volume =

  6. [6]

    Theoretical Computer Science , volume =

    Mart\'in Abadi and Leslie Lamport , title =. Theoretical Computer Science , volume =

  7. [7]

    Floyd , title =

    Robert W. Floyd , title =. Proc. Symposia in Applied Mathematics , volume =. 1967 , publisher =

    1967

  8. [8]

    Zohar Manna and Amir Pnueli , title =

Show all 12 references
  1. [9]

    POPL , pages =

    Patrick Cousot and Radhia Cousot , title =. POPL , pages =

  2. [10]

    C. A. R. Hoare , title =. Communications of the ACM , volume =

  3. [11]

    , title =

    O'Hearn, Peter W. , title =. Proc. ACM Program. Lang. , month = dec, articleno =. 2019 , issue_date =. doi:10.1145/3371078 , abstract =

    2019 doi

  4. [12]

    Automatic Inference of Necessary Preconditions

    Cousot, Patrick and Cousot, Radhia and F \"a hndrich, Manuel and Logozzo, Francesco. Automatic Inference of Necessary Preconditions. Verification, Model Checking, and Abstract Interpretation. 2013

    2013

Pith tools

Reviewed June 29, 2026 · model on record in the stance chip above.