2010 · 48 citations · 22 references
ComputingComputer ScienceFormal MethodsLogicProgramming LanguagesBoolean AlgebraPredicate LogicPropositional LogicPropositional CalculusPropositional ReasoningPropositional RepresentationSeparation LogicUndecidability
Separation logic has proven an effective formalism for the analysis of memory-manipulating programs. We show that the purely propositional fragment of separation logic is undecidable. In fact, for any choice of concrete heap-like model of separation logic, validity in that model remains undecidable. Besides its intrinsic technical interest, this result also provides new insights into the nature of decidable fragments of separation logic. In addition, we show that a number of propositional systems which approximate separation logic are undecidable as well. In particular, these include both Boolean BI and Classical BI. All of our undecidability results are obtained by means of a single direct encoding of Minsky machines.
22
Computation: Finite and Infinite Machines.
D. A. Clarke, Marvin Minsky · American Mathematical Monthly · 1968 · 2.6K citations
Separation logic: a logic for shared mutable data structures
John Reynolds · 2003 · 2.2K citations
Effect algebras and unsharp quantum logics
David J. Foulis, M. K. Bennett · Foundations of Physics · 1994 · 868 citations
Computing, Computer Science, Physics +10
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