2013 · 58 citations · 20 references
ComputingComputer ScienceFormal MethodsLogicTheory Of ComputationDeductive VerificationFormal SemanticsProof AssistantsProof ComplexityProof TheoryTheorem ProvingFormal Proof SystemsHoare TriplesOperational SemanticsProgram VerificationProof CertificatesProof SystemsSmall-step SemanticsSoundness
This paper introduces (one-path) reachability logic, a language-independent proof system for program verification, which takes an operational semantics as axioms and derives reachability rules, which generalize Hoare triples. This system improves on previous work by allowing operational semantics given with conditional rewrite rules, which are known to support all major styles of operational semantics. In particular, Kahn's big-step and Plotkin's small-step semantic styles are now supported. The reachability logic proof system is shown sound (i.e., partially correct) and (relatively) complete. Reachability logic thus eliminates the need to independently define an axiomatic and an operational semantics for each language, and the nonnegligible effort to prove the former sound and complete w.r.t. the latter. The soundness result has also been formalized in Coq, allowing reachability logic derivations to serve as formal proof certificates that rely only on the operational semantics.
20
Separation logic: a logic for shared mutable data structures
John Reynolds · 2003 · 2.2K citations
A Structural Approach to Operational Semantics
Gordon Plotkin · 2004 · 2K citations
A Syntactic Approach to Type Soundness
Andy Wright, Matthias Felleisen · Information and Computation · 1994 · 1.1K citations
Gérard Berry, Gérard Boudol · Theoretical Computer Science · 1992 · 817 citations
The Logic of Bunched Implications
Peter W. O’Hearn, David Pym · Bulletin of Symbolic Logic · 1999 · 474 citations
Humanities, Mathematics, Logic +12