@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
}