Skip to main content

Research Repository

Advanced Search

Complexity classification in qualitative temporal constraint reasoning

Jonsson, P.; Krokhin, A.

Complexity classification in qualitative temporal constraint reasoning Thumbnail


Authors

P. Jonsson



Abstract

We study the computational complexity of the qualitative algebra which is a temporal constraint formalism that combines the point algebra, the point-interval algebra and Allen's interval algebra. We identify all tractable fragments and show that every other fragment is NP-complete.

Citation

Jonsson, P., & Krokhin, A. (2004). Complexity classification in qualitative temporal constraint reasoning. Artificial Intelligence, 160(1-2), 35-51. https://doi.org/10.1016/j.artint.2004.05.010

Journal Article Type Article
Publication Date Dec 1, 2004
Deposit Date Mar 29, 2010
Publicly Available Date Mar 28, 2024
Journal Artificial Intelligence
Print ISSN 0004-3702
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 160
Issue 1-2
Pages 35-51
DOI https://doi.org/10.1016/j.artint.2004.05.010
Keywords Temporal reasoning, Constraint satisfaction, Computational complexity.

Files





You might also like



Downloadable Citations