Complexity classification in qualitative temporal constraint reasoning

被引：5

作者：

Jonsson, P ^{[1
]}

Krokhin, A

机构：

[1] Linkoping Univ, Dept Comp & Informat Sci, SE-58183 Linkoping, Sweden

[2] Univ Warwick, Dept Comp Sci, Coventry CV4 7AL, W Midlands, England

来源：

ARTIFICIAL INTELLIGENCE | 2004年 / 160卷 / 1-2期

基金：

英国工程与自然科学研究理事会;

关键词：

temporal reasoning; constraint satisfaction; computational complexity;

D O I：

10.1016/j.artint.2004.05.010

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete. (C) 2004 Elsevier B.V. All rights reserved.

引用

页码：35 / 51

页数：17