D. Lücke, T. Mossakowski, und D. Wolter. Spatial Cognition VI 2008, Volume 5248 von Lecture Notes in Computer Science, Seite 426-440. Springer, (2008)
Zusammenfassung
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.
%0 Conference Paper
%1 LueckeEtAl08
%A Lücke, Dominik
%A Mossakowski, Till
%A Wolter, Diedrich
%B Spatial Cognition VI 2008
%D 2008
%E Freksa, Christian
%E Newcombe, Nora S.
%E Gaerdenfors, Peter
%I Springer
%K imported
%P 426-440
%T Qualitative reasoning about convex relations
%U http://dx.doi.org/10.1007/978-3-540-87601-4_30
%V 5248
%X 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.
%@ 978-3-540-87600-7
@inproceedings{LueckeEtAl08,
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.
},
added-at = {2016-08-05T15:59:03.000+0200},
author = {L{\"u}cke, Dominik and Mossakowski, Till and Wolter, Diedrich},
biburl = {https://www.bibsonomy.org/bibtex/210a44879aa4c1d1ff5245ff0743ea10c/tillmo},
booktitle = {Spatial Cognition VI 2008},
editor = {Freksa, Christian and Newcombe, Nora S. and Gaerdenfors, Peter},
interhash = {0f9ddc217a7d632d1aa1ec2b07c72994},
intrahash = {10a44879aa4c1d1ff5245ff0743ea10c},
isbn = {978-3-540-87600-7},
keywords = {imported},
pages = {426-440},
pdfurl = {http://www.informatik.uni-bremen.de/~till/papers/ConvexRelations.pdf},
publisher = {Springer},
series = {Lecture Notes in Computer Science},
status = {Reviewed},
timestamp = {2016-08-05T15:59:03.000+0200},
title = {Qualitative reasoning about convex relations},
url = {http://dx.doi.org/10.1007/978-3-540-87601-4_30},
volume = 5248,
year = 2008
}