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 |
