Write a Blog >>
Mon 20 Jan 2020 10:30 - 11:00 at Conde - Research Papers

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 Jan

Displayed time zone: Saskatchewan, Central America change