A fast algorithm and datalog inexpressibility for temporal reasoning
A fast algorithm and datalog inexpressibility for temporal reasoning
复制标题
用于时间推理的快速算法和数据记录不可表达性
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Jan Kára
中科院分区：
文献类型：
--
作者：
M. Bodirsky;Jan Kára
我们引入了一种新的易处理的时态约束语言，它严格包含了Bürkert和Nebel的Ord-Horn语言和AND/OR优先约束类。我们为这种语言提出的算法决定了一组给定的约束是否在时间上是一致的，即在输入大小上是二次的。我们还证明，（不像奥德霍恩）这种语言的约束满足问题不能解决的数据库或建立本地一致性。
We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Bürkert and Nebel and the class of AND/OR precedence constraints. The algorithm we present for this language decides whether a given set of constraints is consistent in time that is quadratic in the input size. We also prove that (unlike Ord-Horn) the constraint satisfaction problem of this language cannot be solved by Datalog or by establishing local consistency.