论文标题
在带有数据的本地一阶逻辑的存在片段上
On the Existential Fragments of Local First-Order Logics with Data
论文作者
论文摘要
我们研究了一阶逻辑，这些逻辑是从无限域中携带有限数量的数据值的无序结构，可以比较WRT。平等。由于这种逻辑的满足性问题通常是不可确定的，因此在先前的工作中，我们引入了一个局部片段家庭，将量化限制在给定参考点的社区。我们在这里提供了该局部逻辑的存在性片段的确切复杂性表征，具体取决于每个元素和所考虑邻域的半径的数据值数量。
We study first-order logic over unordered structures whose elements carry a finite number of data values from an infinite domain which can be compared wrt. equality. As the satisfiability problem for this logic is undecidable in general, in a previous work, we have introduced a family of local fragments that restrict quantification to neighbourhoods of a given reference point. We provide here the precise complexity characterisation of the satisfiability problem for the existential fragments of this local logic depending on the number of data values carried by each element and the radius of the considered neighbourhoods.
