Complexity classification in qualitative temporal constraint reasoning

Jonsson, P.; Krokhin, A.

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: Apr 7, 2010
• 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.
• Public URL: https://durham-repository.worktribe.com/output/1564631