Solving minimal constraint networks in qualitative spatial and temporal reasoning

Publication Type:
Conference Proceeding
Citation:
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:
2012-11-07
Full metadata record
Files in This Item:
Filename Description Size
Thumbnail2011006781OK.pdf1.01 MB
Adobe PDF
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: