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

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