A Fast Algorithm and Datalog Inexpressibility for Temporal Reasoning

被引：15

作者：

Bodirsky, Manuel ^{[1
]}

Kara, Jan ^{[2
]}

机构：

[1] Ecole Polytech, CNRS, LIX, Lab Informat,UMR 6171, F-91128 Paris, France

[2] Charles Univ Prague, Fac Math & Phys, Prague 10000 10, Czech Republic

来源：

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC | 2010年 / 11卷 / 03期

关键词：

Algorithms; Languages; Constraint satisfaction; temporal reasoning; computational complexity; Ord-Horn; algorithms; Datalog; precedence constraints; COMPLEXITY; CONSTRAINTS;

D O I：

10.1145/1740582.1740583

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We introduce a new tractable temporal constraint language, which strictly contains the Ord-Horn language of Burkert 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.

引用

页数：21

共 31 条

[1] MAINTAINING KNOWLEDGE ABOUT TEMPORAL INTERVALS
ALLEN, JF
[J]. COMMUNICATIONS OF THE ACM, 1983, 26 (11) : 832 - 843
[2] [Anonymous], 2002, MODEL THEORY INTRO
[3] BODIRSKY M, 2006, P STACS 06, P646
[4] BODIRSKY M, 2008, P 40 ANN ACM S THEOR, P29
[5] Bodirsky M., 2008, P STACS 06
[6] Classifying the complexity of constraints using finite algebras
Bulatov, A
Jeavons, P
Krokhin, A
[J]. SIAM JOURNAL ON COMPUTING, 2005, 34 (03) : 720 - 742
[7] CREIGNOU N, 2005, COMPLEXITY CLAUSAL C
[8] Dechter R., 2003, Constraint processing
[9] Diestel R., 2005, GRAPH THEORY, VThird
[10] Twenty-one large tractable subclasses of Allen's algebra
Drakengren, T
Jonsson, P
[J]. ARTIFICIAL INTELLIGENCE, 1997, 93 (1-2) : 297 - 319

← 1 2 3 4 →