The Library
Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra
Tools
UNSPECIFIED (2003) Reasoning about temporal relations: The tractable subalgebras of Allen's interval algebra. JOURNAL OF THE ACM, 50 (5). pp. 591-640. ISSN 0004-5411.
Research output not available from this repository.
Request-a-Copy directly from author or use local Library Get it For Me service.
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.
Item Type: | Journal Article | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||
Journal or Publication Title: | JOURNAL OF THE ACM | ||||
Publisher: | ASSOC COMPUTING MACHINERY | ||||
ISSN: | 0004-5411 | ||||
Official Date: | September 2003 | ||||
Dates: |
|
||||
Volume: | 50 | ||||
Number: | 5 | ||||
Number of Pages: | 50 | ||||
Page Range: | pp. 591-640 | ||||
Publication Status: | Published |
Data sourced from Thomson Reuters' Web of Knowledge
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |