[BibTeX] [RIS]
Qualitative reasoning about convex relations
Type of publication: Inproceedings
Citation: LueckeEtAl08
Booktitle: Spatial Cognition VI 2008
Series: Lecture Notes in Computer Science
Volume: 5248
Year: 2008
Pages: 426-440
Publisher: Springer
ISBN: 978-3-540-87600-7
DOI: 10.1007/978-3-540-87601-4_30
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.
Userfields: bdsk-url-1={http://dx.doi.org/10.1007/978-3-540-87601-4_30}, pdfurl={http://www.informatik.uni-bremen.de/~till/papers/ConvexRelations.pdf}, project={I4-SPIN}, status={Reviewed},
Keywords:
Authors Lücke, Dominik
Mossakowski, Till
Wolter, Diedrich
Editors Freksa, Christian
Newcombe, Nora S.
Gaerdenfors, Peter
Attachments
  • http://dx.doi.org/10.1007/978-...
  • http://www.informatik.uni-brem...
Notes
    Topics