Jonsson, P. and Krokhin, A. (2004) 'Complexity classification in qualitative temporal constraint reasoning.', Artificial Intelligence., 160 (1-2). pp. 35-51.
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.
Item Type: | Article |
---|---|
Keywords: | Temporal reasoning, Constraint satisfaction, Computational complexity. |
Full text: | (AM) Accepted Manuscript Download PDF (287Kb) |
Status: | Peer-reviewed |
Publisher Web site: | http://dx.doi.org/10.1016/j.artint.2004.05.010 |
Date accepted: | No date available |
Date deposited: | 07 April 2010 |
Date of first online publication: | December 2004 |
Date first made open access: | No date available |
Save or Share this output
Export: | |
Look up in GoogleScholar |