Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen’s Interval Algebra

Bernhard Nebel, Hans-Jürgen Bürckert

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. In fact, it is the unique greatest tractable subclass amongst the subclasses that contain all basic relations.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.