.png){kind=icon}
.png){kind=icon}
Return
An EXPTIME-complete entailment problem in separation logic
.png){kind=icon}
PRE
AI
P
DOI：10.1093/logcom/exag008.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Separation logic (SL) is extensively employed in verification to analyse programmes that manipulate dynamically allocated memory. The entailment problem, when dealing with inductively defined predicates or data constraints, is undecidable for SL formulas. Our focus is on addressing a specific fragment of this issue, wherein the consequent is restricted to clauses of some particular form, devoid of inductively defined predicates. We present an algorithm designed to determine the validity of such entailments and demonstrate that the problem is decidable and ExpTime complete under some conditions on the data theory. This algorithm serves the purpose of verifying that the data structures outlined by a given SL formula (the antecedent) adhere to certain shape constraints expressed by the consequent.
Keywords:
separation logic
inductive reasoning
entailment problem
complexity
Journal
J
IF:
0
Papers:
44
Citations:
0
Organization
Cited Papers