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: |