liu.seSearch for publications in DiVA
Change search
ReferencesLink to record
Permanent link

Direct link
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
University of Warwick, Coventry, United Kingdom, Department of Computer Science, University of Warwick, Coventry, CV4 7AL, United Kingdom.
University of Oxford, Oxford, United Kingdom, Computing Laboratory, University of Oxford, Oxford, OX1 3QD, United Kingdom.
Linköping University, The Institute of Technology. Linköping University, Department of Computer and Information Science, TCSLAB - Theoretical Computer Science Laboratory.
2003 (English)In: Journal of the ACM, ISSN 0004-5411, Vol. 50, no 5, 591-640 p.Article in journal (Refereed) Published
Abstract [en]

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.

Place, publisher, year, edition, pages
2003. Vol. 50, no 5, 591-640 p.
Keyword [en]
Allen's algebra, Complexity, Dichotomy theorem, NP-completeness, Representing graphs by intervals, Satisfiability of temporal constraints, Tractable cases
National Category
Engineering and Technology
URN: urn:nbn:se:liu:diva-46509DOI: 10.1145/876638.876639OAI: diva2:267405
Available from: 2009-10-11 Created: 2009-10-11 Last updated: 2011-01-13

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Jonsson, Peter
By organisation
The Institute of TechnologyTCSLAB - Theoretical Computer Science Laboratory
In the same journal
Journal of the ACM
Engineering and Technology

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 25 hits
ReferencesLink to record
Permanent link

Direct link