Journal of Logic and Computation · 2009 · 34 citations · 14 references
ComputingComputer ScienceMathematicsFormal MethodsKnowledge RepresentationLogicBoolean AlgebraDirected Acyclic GraphsResource Allocation GraphsSeparation LogicTableau Algorithms
Separation logic (SL) is often presented as an assertion language for reasoning about mutable data structures. As recent results about verification in SL have mainly been achieved from a model-checking point of view, our aim in this article is to study SL from a complementary proof-theoretic perspective in order to provide results about proof search in SL. We begin our study with a fragment of SL, denoted SLP, where first-order quantifiers, variables and equality are removed. We first define specific structures, called resource graphs, that capture SLP models by considering heaps as resources via a labelling process. We then provide a tableau calculus that allows us to build such resource graphs from which either proofs, or countermodels can be generated. We finally prove soundess, completeness and termination of our tableau calculus before discussing extensions to various fragments of SL (including full SL) and the related decidability issues.
14
Separation logic: a logic for shared mutable data structures
John Reynolds · 2003 · 2.2K citations
BI as an assertion language for mutable data structures
Samin Ishtiaq, Peter W. O’Hearn · ACM SIGPLAN Notices · 2011 · 499 citations
The Logic of Bunched Implications
Peter W. O’Hearn, David Pym · Bulletin of Symbolic Logic · 1999 · 474 citations
Humanities, Mathematics, Logic +12
Permission accounting in separation logic
Richard Bornat, Cristiano Calcagno, Peter W. O’Hearn et al. · 2005 · 370 citations
Luca Cardelli, Andrew D. Gordon · 2000 · 351 citations