FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Cyclic Theorem Prover for Separation Logic by Magic Wand

Authors: Koji Nakazawa, Makoto Tatsuta and Daisuke Kimura

Paper Information

Title:Cyclic Theorem Prover for Separation Logic by Magic Wand
Authors:Koji Nakazawa, Makoto Tatsuta and Daisuke Kimura
Proceedings:ADSL Papers
Editor: Nikos Gorogiannis
Keywords:separation logic, symbolic heap, entailment check, cyclic proof, proof search
Abstract:

ABSTRACT. We propose the strong wand and the Factor rule in a cyclic-proof system for the separation-logic entailment checking problem with general inductive predicates. The strong wand is similar to but stronger than the magic wand and is defined syntactically. The Factor rule, which uses the strong wand, is an inference rule for spatial factorization to expose an implicitly allocated cell in inductive predicates. By this rule, we can void getting stuck in the Unfold-Match-Remove strategy. We show a semi-decision algorithm of proof search in the cyclic-proof system with the Factor rule and the experimental results of its prototype implementation.

Pages:19
Talk:Jul 13 11:00 (Session 86A: Proof Theory)
Paper: