Faculty of Computer Science

Research Group Theoretical Computer Science

Oberseminar: Heterogene formale Methoden

Date: 2015, June 3
Time: 11:00
Author: Mossakowski, Till
Title: Left and Right are Harder Than West and East – Qualitative Spatial Reasoning About Relative Orientation


Qualitative spatio-temporal reasoning abstracts from quanitative numerical values. Instead, qualitative concepts know to humans are used, such as “left”, “right”, “front”, “back”, “West”, “East”, “inside”, “touches”, “before” etc.
We introduce the traditional approach to qualitative spatio-temporal reasoning based on composition tables and algebraic closure. While this approach works quite well for time, mereotopology and absolute directions, it has severe limitations for reasoning about relative directions. Indeed, the latter reasoning is computationally hard, namely as hard as deciding satisfiability in the existential theory of the reals, which is located between NP and PSPACE.
We summarize a number of incomplete semi-decision procedures for relative orientation and present the results of a benchmark illustrating the relative effectiveness and efficiency of these procedures.


Back to the Oberseminar web page