REASONING ABOUT TEMPORAL RELATIONS - A MAXIMAL TRACTABLE SUBCLASS OF ALLENS INTERVAL ALGEBRA

被引：224

作者：

NEBEL, B ^{[1
]}

BURCKERT, HJ ^{[1
]}

机构：

[1] GERMAN RES CTR ARTIFICIAL INTELLIGENCE DFKI, D-66123 SAARBRUCKEN, GERMANY

来源：

JOURNAL OF THE ACM | 1995年 / 42卷 / 01期

关键词：

ALGORITHMS; THEORY; CONSTRAINT SATISFACTION; INTERVAL ALGEBRA; QUALITATIVE REASONING; TEMPORAL REASONING;

D O I：

10.1145/200836.200848

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We introduce a new subclass of Alien's interval algebra we call ''ORD-Horn subclass,'' which is a strict superset of the ''pointisable subclass.'' We prove that reasoning in the ORD-Horn subclass is a polynomial-time problem and show that the path-consistency method is sufficient for deciding satisfiability. Further, using an extensive machine-generated case analysis, we show that the ORD-Horn subclass is a maximal tractable subclass of the full algebra (assuming P not equal NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.

引用

页码：43 / 66

页数：24

共 35 条

[31]

VAN BEEK P., Reasoning about qualitative temporal information, Proceedings of the 8th National Conference of the American Association for Artificial Intelligence, pp. 728-734, (1990)

[32]

VAN BEEK P., COHEN R., Exact and approximate reasoning about temporal relations, Comput. Int., 6, pp. 132-144, (1990)

[33]

VILAIN M.B., KAUTZ H.A., Constraint propagation algorithms for temporal reasoning, Proceedings of the 5th National Conference of the American Association for Artificial Intelligence, pp. 377-382, (1986)

[34]

VILAIN M.B., KAUTZ H.A., VAN BEEK P.G., Constraint propagation algorithms for temporal reasoning: A revised report, Readings in Qualitative Reasoning about Physical Systems, pp. 373-381, (1989)

[35]

WEIDA R., LITMAN D., Terminological reasoning with constraint networks and an application to plan recognition, Principles of Knowledge Representation and Reasoning: Proceedings of the 3rd International Conference, pp. 282-293, (1992)

← 1 2 3 4 →