|
|||||
|
|
Complexity classification in qualitative temporal constraint reasoning |
|
| Authors: | Peter Jonsson Andrei Krokhin |
| Affiliation: | aDepartment of Computer and Information Science, Linköpings Universitet, SE-581 83 Linköping, Sweden bDepartment of Computer Science, University of Warwick, UK |
| 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. |
| Keywords: | Temporal reasoning Constraint satisfaction Computational complexity |
| 本文献已被 ScienceDirect 等数据库收录！ | |