Counting in the Two Variable Guarded Logic with Transitivity
Counting in the Two Variable Guarded Logic with Transitivity
复制标题
具有传递性的二变量保护逻辑的计数
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Lidia Tendera
中科院分区：
文献类型：
--
作者：
Lidia Tendera
我们证明，通过功能语句对具有传递保护的二变量保护片段（GF+TG）的扩展是不可判定的。这通过计数量词立即给出了 GF+TG 扩展的不可判定性。结果是最优的，因为具有计数量词的受保护片段的三变量片段和具有传递性的二变量受保护片段都是不可判定的。
我们还表明，GF+TG 的功能扩展（其中功能谓词字母仅出现在防护中）是可判定的，并且具有与 GF+TG 相同的复杂性。该片段捕获了许多表达模式和描述逻辑。
We show that the extension of the two-variable guarded fragment with transitive guards (GF+TG) by functionality statements is undecidable. This gives immediately undecidability of the extension of GF+TG by counting quantifiers. The result is optimal, since both the three-variable fragment of the guarded fragment with counting quantifiers and the two-variable guarded fragment with transitivity are undecidable.
We also show that the extension of GF+TG with functionality, where functional predicate letters appear in guards only, is decidable and of the same complexity as GF+TG. This fragment captures many expressive modal and description logics.