| Publication type: |
Article in Proceedings |
| Author: |
Dominik Lücke, Till Mossakowski, Diedrich Wolter |
| Editor: |
Christian Freksa, Nora S. Newcombe, Peter Gaerdenfors |
| Title: |
Qualitative reasoning about convex relations |
| Book / Collection title: |
Spatial Cognition VI 2008 |
| Volume: |
5248 |
| Page(s): |
426 – 440 |
| Series: |
Lecture Notes in Computer Science |
| Year published: |
2008 |
| Publisher: |
Springer |
| Abstract: |
Various calculi have been designed for qualitative
constraint-based representation and reasoning. Especially for orientation calculi,
it happens that the well-known method of algebraic closure
cannot decide consistency of constraint networks, even when
considering networks over base relations (= scenarios) only. We show that this is
the case for all relative orientation calculi capable of distinguishing between
``left of'' and ``right of''. Indeed, for these calculi, it is not clear whether
efficient (i.e. polynomial) algorithms deciding scenario-consistency exist.
As a partial solution of this problem, we present a technique to decide global consistency in
qualitative calculi. It is applicable to all calculi that employ convex
base relations over the real-valued space R^n and it can be performed in
polynomial time when dealing with convex relations only.
Since global consistency implies consistency, this can be an efficient aid for
identifying consistent scenarios.
This complements the method of algebraic closure which can
identify a subset of inconsistent scenarios.
|
| ISBN: |
978-3-540-87600-7 |
| Internet: |
http://dx.doi.org/10.1007/978-3-540-87601-4_30 |
| PDF Version: |
http://www.informatik.uni-bremen.de/~till/papers/ConvexRelations.pdf |
| Status: |
Reviewed |
| Last updated: |
29. 01. 2010 |
