Workshop on Qualitative Spatial and Temporal Reasoning: Computational Complexity and Algorithms

A workshop at the German Conference on Artificial Intelligence.

Qualitative spatial and temporal reasoning is a subfield of AI that is committed to the study of relational knowledge representation languages. Such languages are used for reasoning about semantically meaningful properties of the represented domain (contact of regions, temporal order, etc.). Allen's interval algebra and the RCC calculi are the most prominent approaches, but many more have been developed. Spatial and temporal domains are typically infinite and exhibit complex structures. Due to their richness and diversity, qualitative spatial and temporal reasoning is confronted with some unique challenges. In particular, analyzing the computational complexity of such problems and developing efficient algorithms have proven to be highly challenging tasks.

This workshop aims to provide a forum for researchers from different fields (including Automated Theorem Proving, Constraint Solving, Logic, Mathematics, Theoretical Computer Science, Qualitative Reasoning) to discuss open problems, methodology, and recent advancements in the field.

In case that you plan to attend the workshop, please write an email to Manuel Bodirsky so that we can keep you informed with news concerning the workshop.

The workshop will be take place in room APB/E007. The table below is also available as PDF.

Time Event
08:50 Opening of Workshop
09:00-10:00 Invited talk: Ivo Duentsch
Boolean contact algebras - Structure and representation
10:00-10:20 Coffee break
10:20-10:45 Leif Sabellek and Thomas Schneider
A Note on Algebraic Closure and Closure under Constraints
10:50-11:15 Peter Jonsson and Victor Lagerkvist
Upper and Lower Bounds on the Time Complexity of Infinite-domain CSPs
11:20-11:45 Johannes Greiner
A Polynomial Time Algorithm for Set Constraints with Cardinality Inequalities
11:45-14:45 Lunch break
14:45-15:10 Frank Dylla, Jan Oliver Wallgrün and Jasper van de Ven
Merging Qualitative Information: Rationality and Complexity
15:15-15:40 Florian Muth
AND/OR Linear Programming for Qualitative Spatial Reasoning
15:40-16:00 Coffee break
16:00-16:45 Invited talk: Matthias Westphal
Qualitative constraint-based reasoning: methods and tools
16:45-17:00 Discussion, Closing
The submission server is closed because the deadline has passed.

Impressum Last update: 02.09.2015