We introduce a new subclass of Allen'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 <> NP). In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations. Copyright 1995 by ACM, Inc.
The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- sequencing and scheduling; I.2.4 [Artificial Intelligence]: Knowledge Representation Formalisms and Methods -- relation systems
General Terms: Algorithms, Theory
Additional Key Words and Phrases: Constraint satisfaction, interval algebra, qualitative reasoning, temporal reasoning
- Martin Charles Golumbic and Ron Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the ACM, 40(5):1108-1133, November 1993.
- L. Henschen and L. Wos. Unit refutations and Horn sets. Journal of the ACM, 21(4):590-605, October 1974.
- Peter B. Ladkin and Roger D. Maddux. On binary constraint problems. Journal of the ACM, 41(3):435-469, May 1994.