ALCOMFT-TR-03-52

A. Krokhin, P. Jeavons and P. Jonsson
Reasoning about temporal relations: The maximal tractable subalgebras of Allen's interval algebra
Warwick. Work package 4. October 2003.

Abstract: Allen's interval algebra is one of the best established formalisms for temporal reasoning. This paper is the final step in the classification of complexity in this algebra. Reasoning in the full Allen's algebra is known to be NP-complete, but eighteen tractable subalgebras have so far been identified; we show here that these are the only possible tractable subalgebras. In other words, we show that Allen's algebra contains exactly eighteen maximal tractable subalgebras, and reasoning in any fragment not entirely contained in one of these subalgebras is NP-complete. We obtain this result by giving a new uniform description of the known maximal tractable subalgebras and then systematically using an algebraic technique for identifying maximal subalgebras with a given property.

keywords: Allen's algebra, complexity, NP-completeness, temporal constraints, tractability

Postscript file: ALCOMFT-TR-03-52.ps.gz (252 kb).