Finite satisfiability for two-variable, first-order logic with one transitive relation is decidable
Finite satisfiability for two-variable, first-order logic with one transitive relation is decidable
复制标题
具有一个传递关系的二变量一阶逻辑的有限可满足性是可判定的
DOI：
10.1002/malq.201700055
复制
发表时间：
2018
影响因子：
0.3
通讯作者：
Pratt-Hartmann I
中科院分区：
文献类型：
--
作者：
Pratt-Hartmann I
我们考虑二变量一阶逻辑，其中需要将单个区别谓词解释为传递关系。我们证明了这个逻辑的有限可满足性问题在三重指数非确定时间内是可判定的。如果传递关系被限制为偏序，复杂性福尔斯下降到双指数非确定性时间。
We consider two‐variable, first‐order logic in which a single distinguished predicate is required to be interpreted as a transitive relation. We show that the finite satisfiability problem for this logic is decidable in triply exponential non‐deterministic time. Complexity falls to doubly exponential non‐deterministic time if the transitive relation is constrained to be a partial order.