Extending the Profile Abstraction for Complete Entailment Checking of Symbolic Heaps of Bounded Treewidth
At TACAS 2019, we published a decision procedure for the entailment problem for symbolic-heap separation logic with inductive definitions of bounded treewidth based on a novel abstraction we called the profile abstraction. Since then, we have discovered an incompleteness issue with that decision procedure, as well as a generalization of the profile abstraction that fixes the issue. In this article, we give a high-level discussion of the approach of our TACAS paper, identify the reason for its incompleteness, and explain the necessary changes to obtain a complete decision procedure while retaining the same asymptotic complexity. A complementary article with a full formalization of the extended decision procedure is currently under preparation.
Extending the Profile Abstraction for Complete Entailment Checking of Symbolic Heaps of Bounded Treewidth (main.pdf) | 657KiB |
Mon 20 JanDisplayed time zone: Saskatchewan, Central America change
10:30 - 12:30 | |||
10:30 30mResearch paper | Extending the Profile Abstraction for Complete Entailment Checking of Symbolic Heaps of Bounded Treewidth ADSL File Attached | ||
11:00 30mResearch paper | Steel: scaling up memory reasoning for F* ADSL File Attached | ||
11:30 30mResearch paper | Strong-Separation Logic ADSL File Attached | ||
12:00 30mResearch paper | The Lower Bound of Decidable Entailments in Separation Logic with Inductive Definitions ADSL Pre-print File Attached |