On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity

机译：具有传递性的受保护片段的有限可满足性问题

获取原文

获取原文并翻译 | 示例

页面导航

摘要
著录项
相似文献
相关主题

摘要

We study the finite satisfiability problem for the guarded fragment with transitivity. We prove that in case of one transitive predicate the problem is decidable and its complexity is the same as the general satisfiability problem, i.e. 2ExPTIME-complete. We also show that finite models for sentences of GF with more transitive predicate letters used only in guards have essentially different properties than infinite ones.

机译：我们研究了具有可传递性的受保护片段的有限可满足性问题。我们证明，在一个及物谓词的情况下，该问题是可判定的，并且其复杂性与一般可满足性问题相同，即2ExPTIME-complete。我们还表明，具有仅在警卫中使用的更多及物谓词的GF句子的有限模型与无限模型具有本质上不同的属性。

著录项

来源
《International Conference on Logic for Programming, Artificial Intelligence, and Reasoning(LPAR 2005); 20051202-06; Montego Bay(JM)》|2005年|P.307-321|共15页
会议地点 Montego Bay(JM)
作者
Wieslaw Szwast; Lidia Tendera;
展开▼
作者单位

Institute of Mathematics and Informatics, Opole University, Poland;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类人工智能理论;
关键词
finite model; guarded fragment; transitivity; decision problem; computational complexity;

机译：有限模型;保护片段;传递性;决策问题;计算复杂度;

相似文献

外文文献
中文文献
专利

1. Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants [J] . Kieronski Emanuel, Tendera Lidia ACM transactions on computational logic . 2018,第2期

机译：具有传递卫兵和相关变体的两变量守卫片段的有限可满足性
2. Finite Satisfiability of Unary Negation Fragment with Transitivity [J] . Daniel Danielski, Emanuel Kieronski LIPIcs : Leibniz International Proceedings in Informatics . 2019,第2015期

机译：一元否定片段具有传递性的有限满足性
3. On the complexity of the two-variable guarded fragment with transitive guards [J] . Kieronski E Information and computation . 2006,第11期

机译：具有传递守卫的二元守卫碎片的复杂性
4. On Finite Satisfiability of the Guarded Fragment with Equivalence or Transitive Guards [C] . Emanuel Kieroriski, Lidia Tendera International Conference on Logic for Programming, Artificial Intelligence and Reasoning(LPAR 2007); 20071015-19; Yerevan(AM) . 2007

机译：具有等价或传递保护的受保护片段的有限可满足性
5. Path-Functional Dependencies and the Two-Variable Guarded Fragment with Counting [D] . Kourtis, Georgios. 2017

机译：路径功能依赖性和带计数的两个变量保护片段
6. Does the optimal position of the acetabular fragment should be within the radiological normal range for all developmental dysplasia of the hip? A patient-specific finite element analysis [O] . Xuyi Wang, Jianping Peng, De Li, 2016

机译：对于所有髋关节发育不良髋臼碎片的最佳位置是否应在放射正常范围内？特定于患者的有限元分析
7. Finite Satisfiability of the Two-Variable Guarded Fragment with Transitive Guards and Related Variants [O] . Kieronski, Emanuel, Tendera, Lidia 2018

机译：具有时滞的双变量保护碎片的有限可满足性传递卫兵和相关变种
8. Boolean Satisfiability with Transitivity Constraints [R] . Bryan, R. E. , Velev, M. N. 2000

机译：传递约束的布尔可满足性

On the Finite Satisfiability Problem for the Guarded Fragment with Transitivity

摘要

著录项

相似文献

相关主题

期刊订阅