{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T11:22:37Z","timestamp":1790076157619,"version":"4.0.1"},"reference-count":0,"publisher":"EasyChair","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"<jats:p>The entailment between separation logic formul\u00e6 with inductive predicates, also known as sym- bolic heaps, has been shown to be decidable for a large class of inductive definitions [7]. Recently, a 2-EXPTIME algorithm was proposed [10, 14] and an EXPTIME-hard bound was established in [8]; however no precise lower bound is known. In this paper, we show that deciding entailment between predicate atoms is 2-EXPTIME-hard. The proof is based on a reduction from the membership problem for exponential-space bounded alternating Turing machines [5].<\/jats:p>","DOI":"10.29007\/f5wh","type":"proceedings-article","created":{"date-parts":[[2020,5,27]],"date-time":"2020-05-27T18:10:11Z","timestamp":1590603011000},"page":"191-169","source":"Crossref","is-referenced-by-count":8,"title":["Entailment Checking in Separation Logic with Inductive Definitions is 2-EXPTIME hard"],"prefix":"10.29007","volume":"73","author":[{"given":"Mnacho","family":"Echenim","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Radu","family":"Iosif","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicolas","family":"Peltier","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"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:14Z","timestamp":1590603014000},"score":1,"resource":{"primary":{"URL":"https:\/\/easychair.org\/publications\/paper\/DdNg"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"references-count":0,"URL":"https:\/\/doi.org\/10.29007\/f5wh","relation":{},"ISSN":["2398-7340"],"issn-type":[{"value":"2398-7340","type":"print"}],"subject":[]}}