Skip to main content

Research Repository

Advanced Search

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

Krokhin, A.; Jeavons, P.; Jonsson, P.

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


Authors

P. Jeavons

P. Jonsson



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.

Citation

Krokhin, A., Jeavons, P., & Jonsson, P. (2003). Reasoning about temporal relations : the maximal tractable subalgebras of Allen's interval algebra. Journal of the ACM, 50(5), 591-640. https://doi.org/10.1145/876638.876639

Journal Article Type Article
Publication Date 2003-09
Deposit Date Jan 23, 2009
Publicly Available Date Mar 28, 2024
Journal Journal of the Association for Computing Machinery.
Print ISSN 0004-5411
Publisher Association for Computing Machinery (ACM)
Peer Reviewed Peer Reviewed
Volume 50
Issue 5
Pages 591-640
DOI https://doi.org/10.1145/876638.876639
Keywords Algorithms, Theory, Complexity, Dichotomy theorem, NPcompleteness.
Publisher URL http://doi.acm.org/10.1145/876638.876639

Files

Accepted Journal Article (424 Kb)
PDF

Copyright 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, http://doi.acm.org/10.1145/380752.380868.





You might also like



Downloadable Citations