Research Group on the Foundations of Artificial Intelligence Department of Computer Science University of Freiburg

Publications (Alexander Scivos)

Journal Articles:

• Bernhard Nebel and Alexander Scivos, Formal Properties of Constraint Calculi for Qualitative Spatial Reasoning, in: Künstliche Intelligenz , 2002. (gzipped postscript file) (pdf file) (bib entry)

  Abstract: In the previous two decades, a number of qualitative constraint calculi have been developed, which are used to represent and reason about spatial configurations. A common property of almost all of these calculi is that reasoning in them can be understood as solving a binary constraint satisfaction problem over infinite domains. The main algorithmic method that is used is constraint propagation in the form of the path-consistency method. This approach can be applied to a wide range of different aspects of spatial reasoning. We describe how to make use of this representation and reasoning technique and point out the possible problems one might encounter.

Conference Papers:

• Alexander Scivos, The Finest of its Class: The Practical Natural Point-based Ternary Calculus LR for Qualitative Spatial Reasoning , in: Spatial Cognition IV, 2004. (gzipped postscript file) (pdf file) (bib entry)

  Abstract: We develop a theory for ternary point-based calculi such that the relations are invariant when all points are mapped by rotations, scalings or translations and propose methods to determine arbitrary transformations and compositions of such relations. We argue that calculi based on such relation systems should satisfy two criteria. First, the relation system should be closed under transformations, compositions and intersections and have a finite base that is jointly exhaustive and pairwise. This implies that the well-known path consistency algorithm can be used to conclude implicit knowledge without any loss of information. If this is the case, we call the calculus {\em practical}. Second, we say that a relation system is {\em natural} if all relations and their complements give rise to sets of points that are connected. The main result of the paper is then the identification of a maximally refined calculus amongst the practical natural RST calculi, which turns out to be very similar to Ligozat's flip-flop calculus. From that it follows, e.g., that there is no finite refinement of the TPCC calculus by Moratz et al that is closed under transformations, composition, and intersection.

• Alexander Scivos and Bernhard Nebel, Double-Crossing: Decidability and Computational Complexity of a Qualitative Calculus for Navigation, in: {Spatial Information Theory: Foundations of Geographic Information Science (COSIT-2001). (bib entry)

  Abstract: (will be here soon)

Workshop Papers:

Other Papers:

• Alexander Scivos, Einführung in eine Theorie der ternären RST-Kalküle für qualitatives räumliches Schließen, Diplomarbeit (Master's Thesis), Albert-Ludwigs-Universität Freiburg, 2000. (gzipped postscript file) (pdf file) (bib entry)

  Abstract: (will be published soon)

• Alexander Scivos, Roboternavigation, Studienarbeit, Albert-Ludwigs-Universität Freiburg, 1998. German language only. (gzipped postscript file) (bib entry)

  Abstract:

Erdös Number: 5 (via Bernhard Nebel)

scivos@informatik.uni-freiburg.de, 14. November 2004