Access Restriction

Author Krokhin, Andrei ♦ Jeavons, Peter ♦ Jonsson, Peter
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2003
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Allen's algebra ♦ NP-completeness ♦ Complexity ♦ Dichotomy theorem ♦ Representing graphs by intervals ♦ Satisfiability of temporal constraints ♦ Tractable cases
Abstract 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.
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2003-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 50
Issue Number 5
Page Count 50
Starting Page 591
Ending Page 640

Open content in new tab

   Open content in new tab
Source: ACM Digital Library