论文标题
与归纳定义的分离逻辑中的可决定性统一
Unifying Decidable Entailments in Separation Logic with Inductive Definitions
论文作者
论文摘要
分离逻辑中的$φ\ψ$ψ$ cite \ cite {ishtiaqohearn01，reynolds02}之间，在方程式的分开连接之间（$ x \ iseq y $ and $ x \ x \ x \ not \ iseq y $） （$ p（x_1，\ ldots，x_n）$）原子，通过一组有限的归纳规则来解释，通常是不确定的。对归纳定义集的某些限制导致了可决定的综合问题。当前，基于两个限制，有两个这样的可定义类，称为\ emph {stupmurand} \ cite {iosifrogalewiczsimacek13，katelaanmathejazuleger19，pz20}和\ emph {cripted}通过\ cite {pz20}和\ cite {eip21a}的独立证明，这两个类别都显示在\ Twiexptime \中，并且已经给出了\ cite {eip21a}。在本文中，我们通过分别分别分别适用于左 - （$φ$）和右 - （$ψ$）手部的条件来严格概括限制类别。我们将这个称为\ emph {safe}的概括的类别减少到已建立的类别。加上将建立的限制为限制的问题的减少，这种新的还原结束了循环，并表明三类的零件问题（分别建立，限制和安全）形成了一个单一的，统一的，\ twixptime-complete类。
The entailment problem $φ\models ψ$ in Separation Logic \cite{IshtiaqOHearn01,Reynolds02}, between separated conjunctions of equational ($x \iseq y$ and $x \not\iseq y$), spatial ($x \mapsto (y_1,\ldots,y_\rank)$) and predicate ($p(x_1,\ldots,x_n)$) atoms, interpreted by a finite set of inductive rules, is undecidable in general. Certain restrictions on the set of inductive definitions lead to decidable classes of entailment problems. Currently, there are two such decidable classes, based on two restrictions, called \emph{establishment} \cite{IosifRogalewiczSimacek13,KatelaanMathejaZuleger19,PZ20} and \emph{restrictedness} \cite{EIP21a}, respectively. Both classes are shown to be in \twoexptime\ by the independent proofs from \cite{PZ20} and \cite{EIP21a}, respectively, and a many-one reduction of established to restricted entailment problems has been given \cite{EIP21a}. In this paper, we strictly generalize the restricted class, by distinguishing the conditions that apply only to the left- ($φ$) and the right- ($ψ$) hand side of entailments, respectively. We provide a many-one reduction of this generalized class, called \emph{safe}, to the established class. Together with the reduction of established to restricted entailment problems, this new reduction closes the loop and shows that the three classes of entailment problems (respectively established, restricted and safe) form a single, unified, \twoexptime-complete class.
