Name
Abstract | ||
|---|---|---|
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 ϕ is like an ordinary representation, but instead of requiring that (a;b)ϕ is the composition aϕ∘bϕ of the relations aϕ and bϕ, as we do for ordinary representations, we only require that cϕ⊇aϕ∘bϕ⇔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. |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1016/j.tcs.2019.02.033 | Theoretical Computer Science |
Keywords | DocType | Volume |
Qualitative calculus,Constraint network,Relation algebra,Representation,Non-associative | Journal | 768 |
ISSN | Citations | PageRank |
0304-3975 | 0 | 0.34 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robin Hirsch | 1 | 46 | 8.21 |
| Marcel Jackson | 2 | 62 | 11.86 |
| Tomasz Kowalski | 3 | 124 | 24.06 |
| Todd Niven | 4 | 101 | 6.11 |