Manuel Bodirsky

Qualitative Temporal and Spatial Reasoning Revisited

With Hubie Chen. Journal of Logic and Computation 2009, doi: 10.1093/logcom/exp025. An extended abstract of this paper appeared in the proceedings of the 6th EACSL Annual Conference on Computer Science and Logic (CSL07).

Abstract

Establishing local consistency is one of the main algorithmic techniques in temporal and spatial reasoning. A central question for the various proposed temporal and spatial constraint languages is whether local consistency implies global consistency. Showing that a constraint language has this ``local-to-global'' property implies polynomial-time tractability of the constraint language, and has further pleasant algorithmic consequences. In the present paper, we study the ``local-to-global'' property by making use of a recently established connection of this property with universal algebra. Roughly speaking, the connection shows that this property is equivalent to the presence of a so-called quasi near-unanimity polymorphism of the constraint language. We obtain new algorithmic results and give very concise proofs of previously known theorems. Our results concern well-known and heavily studied formalisms such as the poin t algebra and its extensions, Allen's interval algebra, and the spatial reasoning language RCC-5.

Download

Download: the journal version of this paper is freely available from the publisher: pdf.


last modified 05/07 (Manuel Bodirsky)