Qualitative Temporal and Spatial Reasoning Revisited
Establishing local consistency is one of the main algorithimic 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 F has this 'local-to-global' property implies polynomial-time tractability of the constraint language, and has further pleasant algorithmic consequences. In the present article. 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 (QNU) polymorphism of the constraint language. We obtain new algorithmic results and give very concise proof's of previously known theorems. Our results concern well-known and heavily studied formalisms such as (he point algebra, Allen's interval algebra and the spatial reasoning language RCC-5.
spatial reasoning consistency temporal reasoning constraint satisfaction computational complexity near-unanimity operations