Algebraic foundations for qualitative calculi and networks

摘要

Binary Constraint Problems have traditionally been considered as Network Satisfaction Problems over some relation algebra. A constraint network is satisfiable if its nodes can be mapped into some representation of the relation algebra in such a way that the constraints are preserved. A qualitative representation phi is like an ordinary representation, but instead of requiring that (a ; b)(phi) is the composition a(phi) o b(phi) of the relations a(phi) and b(phi), as we do for ordinary representations, we only require that c(phi) superset of a(phi) o b(phi) double left right arrow c >= a ; b, for each c in the algebra. A constraint network is qualitatively satisfiable if its nodes can be mapped to elements of a qualitative representation, preserving the constraints. If a constraint network is satisfiable then it is clearly qualitatively satisfiable, but the converse can fail, as we show. However, for a wide range of relation algebras including the point algebra, the Allen Interval Algebra, RCC8 and many others, a network is satisfiable if and only if it is qualitatively satisfiable.