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
关键词
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 条
[1]  
ALLEN J.F., Maintaining knowledge about temporal intervals, Commun. ACM, 26, 11, pp. 832-843, (1983)
[2]  
ALLEN J.F., Towards a general theory of action and time, Artif. Int., 23, 2, pp. 123-154, (1984)
[3]  
ALLEN J.F., Temporal reasoning and planning, Reasoning about Plans, pp. 1-67, (1991)
[4]  
ALLEN J.F., HAYES P.J., A common-sense theory of time, Proceedings of the 9th International Joint Conference on Artificial Intelligence, pp. 528-531, (1985)
[5]  
ALLEN J.F., KOOMEN J.A., Planning using a temporal world model, Proceedings of the 8th International Joint Conference on Artificial Intelligence, pp. 741-747, (1983)
[6]  
ANDRE E., GRAF W., HEINSOHN J., NEBEL B., PROFITLICH H.-J., RIST T., WAHLSTER W., PPP: Personalized plan-based presenter-Project Proposal, (1993)
[7]  
DOWLING W.F., GALLIER J.H., Linear time algorithms for testing the satisfiability of propositional Horn formula, J. Logic Prog., 3, pp. 267-284, (1984)
[8]  
FEINER S.K., LITMAN D.J., MCKEOWN K.R., PASSONNEAU R.J., Towards coordinated temporal multimedia presentation, Intelligent Multi Media, pp. 139-147, (1993)
[9]  
FREKSA C., Temporal reasoning based on semi-intervals, Artif. Int., 54, 1-2, pp. 199-227, (1992)
[10]  
FREUDER E.C., Synthesizing constraint expressions, Commun. ACM, 21, 11, pp. 958-966, (1978)