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

共 23 条

[1] MAINTAINING KNOWLEDGE ABOUT TEMPORAL INTERVALS [J].

ALLEN, JF .

COMMUNICATIONS OF THE ACM, 1983, 26 (11) :832-843

[2]

BALBIANI P, 2002, P 4 INT WORKSH FRONT, P162

[3] Reasoning on interval and point-based disjunctive metric constraints in temporal contexts [J].

Barber, F .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 2000, 12 :35-86

[4] Point algebras for temporal reasoning: Algorithms and complexity [J].

Broxvall, M ;

Jonsson, P .

ARTIFICIAL INTELLIGENCE, 2003, 149 (02) :179-220

[5] Eight maximal tractable subclasses of Allen's algebra with metric time [J].

Drakengren, T ;

Jonsson, P .

JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 1997, 7 :25-45

[6] Twenty-one large tractable subclasses of Allen's algebra [J].

Drakengren, T ;

Jonsson, P .

ARTIFICIAL INTELLIGENCE, 1997, 93 (1-2) :297-319

[7] COMPLEXITY AND ALGORITHMS FOR REASONING ABOUT TIME - A GRAPH-THEORETIC APPROACH [J].

GOLUMBIC, MC ;

SHAMIR, R .

JOURNAL OF THE ACM, 1993, 40 (05) :1108-1133

[8] Expressive power and complexity in algebraic logic [J].

Hirsch, R .

JOURNAL OF LOGIC AND COMPUTATION, 1997, 7 (03) :309-351

[9] A unifying approach to temporal constraint reasoning [J].

Jonsson, P ;

Backstrom, C .

ARTIFICIAL INTELLIGENCE, 1998, 102 (01) :143-155

[10] Computational complexity of relating time points with intervals [J].

Jonsson, P ;

Drakengren, T ;

Bäckström, C .

ARTIFICIAL INTELLIGENCE, 1999, 109 (1-2) :273-295

← 1 2 3 →