Andrei Krokhin, Peter Jeavons and Peter Jonsson
February 2001, 21pp.
Allen's interval algebra is one of the best established formalisms for temporal reasoning. We study those fragments of Allen's algebra that contain a basic relation distinct from the equality relation. We prove that such a fragment is either NP-complete or else contained in some already known tractable subalgebra. We obtain this result by giving a new uniform description of known maximal tractable subalgebras and then systematically using an algebraic technique for description of maximal subalgebras with a given property. This approach avoids the need for extensive computer-assisted search.