We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra.

Krokhin, A. and Jeavons, P. and Jonsson, P. (2003) 'Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra.', Journal of the ACM., 50 (5). pp. 591-640.


Allen's interval algebra is one of the best established formalisms for temporal reasoning. This article provides the final step in the classification of complexity for satisfiability problems over constraints expressed in this algebra. When the constraints are chosen from the full Allen's algebra, this form of satisfiability problem is known to be NP-complete. However, eighteen tractable subalgebras have previously been identified; we show here that these subalgebras include all possible tractable subsets of Allen's algebra. In other words, we show that this 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 dichotomy result by giving a new uniform description of the known maximal tractable subalgebras, and then systematically using a general algebraic technique for identifying maximal subalgebras with a given property.

Item Type:Article
Keywords:Algorithms, Theory, Complexity, Dichotomy theorem, NPcompleteness.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher statement:© ACM, 2003. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Journal of the ACM, Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra, 2003,
Date accepted:No date available
Date deposited:08 September 2010
Date of first online publication:September 2003
Date first made open access:No date available

Save or Share this output

Look up in GoogleScholar