Problems with local consistency for qualitative calculi

Qualitative spatial and temporal reasoning problems are usually expressed in terms of constraint satisfaction problems, with determining consistency as the main reasoning problem. Because of the high complexity of determining consistency, several notions of local consistency, such as path-consistency, k-consistency and corresponding algorithms have been introduced in the constraint community and adopted for qualitative spatial and temporal reasoning. Since most of these notions of local consistency are equivalent for Allen's Interval Algebra, the first and best known calculus of this kind, it is believed by many that these notions are equivalent in general which they are not! In this paper we discuss these various notions of consistency and give examples showing their different behaviours in qualitative reasoning. We argue that algebraic closure, which can be enforced by applying a path-consistcricy algorithm, is the only feasible algebraic method for deciding consistency, and give a heuristic about when algebraic closure decides consistency.