{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T09:28:11Z","timestamp":1750670891891},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>Symbolic-heap separation logic with inductive definitions is a popular formalism for reasoning about heap-manipulating programs. The fragment SLIDbtw introduced by Iosif, Rogalewicz and Simacek, is one of the most expressive fragments with a decidable entailment problem. In recent work, we improved on the original decidability proof by providing a direct model-theoretic construction, obtaining a 2-Exptime upper bound. In this paper, we investigate separation logics built on top of the inductive definitions from SLIDbtw, i.e., logics that feature the standard Boolean and separation-logic operators. We give an almost tight delineation between decidability and undecidabilty. We establish the decidability of the satisfiability problem (in 2-Exptime) of a separation logic with conjunction, disjunction, separating conjunction and guarded forms of negation, magic wand, and septraction. We show that any further generalization leads to undecidabilty (under mild assumptions).<\/jats:p>","DOI":"10.29007\/vkmj","type":"proceedings-article","created":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T18:10:11Z","timestamp":1590603011000},"page":"390-370","source":"Crossref","is-referenced-by-count":3,"title":["Beyond Symbolic Heaps: Deciding Separation Logic With Inductive Definitions"],"prefix":"10.29007","volume":"73","author":[{"given":"Jens","family":"Pagel","sequence":"first","affiliation":[]},{"given":"Florian","family":"Zuleger","sequence":"additional","affiliation":[]}],"member":"11545","event":{"name":"LPAR23. LPAR-23: 23rd International Conference on Logic for Programming, Artificial Intelligence and Reasoning"},"container-title":["EPiC Series in Computing"],"original-title":[],"deposited":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T18:10:11Z","timestamp":1590603011000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/VTGk"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/vkmj","relation":{},"ISSN":["2398-7340"],"issn-type":[{"type":"print","value":"2398-7340"}],"subject":[]}}