ECAI 2004 Conference Paper

[full paper]

Consistency is consistency is consistency

Gerard Ligozat, Jochen Renz

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 point out some of these common consistency myths and give counter-examples to all of them. We discuss the differences between the various notions and argue that only one of them, namely path-consistency, is feasible for deciding consistency. We further give a general necessary and sufficient condition for characterizing the cases where consistency can be decided by enforcing path-consistency.

Keywords: spatial reasoning, temporal reasoning, consistency, path-consistency

Citation: Gerard Ligozat, Jochen Renz: Consistency is consistency is consistency. In R.López de Mántaras and L.Saitta (eds.): ECAI2004, Proceedings of the 16th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2004, pp.1047-1048.