Solving minimal constraint networks in qualitative spatial and temporal reasoning
- Publication Type:
- Conference Proceeding
- Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, 7514 LNCS pp. 464 - 479
- Issue Date:
The minimal label problem (MLP) (also known as the deductive closure problem) is a fundamental problem in qualitative spatial and temporal reasoning (QSTR). Given a qualitative constraint network Γ, the minimal network of Γ relates each pair of variables (x,y) by the minimal label of (x,y), which is the minimal relation between x,y that is entailed by network Γ. It is well-known that MLP is equivalent to the corresponding consistency problem with respect to polynomial Turing-reductions. This paper further shows, for several qualitative calculi including Interval Algebra and RCC-8 algebra, that deciding the minimality of qualitative constraint networks and computing a solution of a minimal constraint network are both NP-hard problems. © 2012 Springer-Verlag.
Please use this identifier to cite or link to this item: