Journal of the ACM Bibliography

Bernhard Nebel and Hans-Jürgen Bürckert. Reasoning about temporal relations: A maximal tractable subclass of Allen's interval algebra. Journal of the ACM, 42(1):43-66, January 1995. [BibTeX entry]

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

Selected references


  • Journal of the ACM homepage
  • Bibliography top level
  • Journal of the ACM Author Index
  • Search the HBP database