TY - GEN
T1 - Problems with local consistency for qualitative calculi
AU - Ligozat, Gerard
AU - Renz, Jochen
PY - 2004
Y1 - 2004
N2 - 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-consistency algorithm, is the only feasible algebraic method for deciding consistency, and give a heuristic about when algebraic closure decides consistency.
AB - 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-consistency algorithm, is the only feasible algebraic method for deciding consistency, and give a heuristic about when algebraic closure decides consistency.
UR - http://www.scopus.com/inward/record.url?scp=85017355161&partnerID=8YFLogxK
M3 - Conference contribution
T3 - Frontiers in Artificial Intelligence and Applications
SP - 1047
EP - 1048
BT - ECAI 2004 - 16th European Conference on Artificial Intelligence, including Prestigious Applications of Intelligent Systems, PAIS 2004 - Proceedings
A2 - de Mantaras, Ramon Lopez
A2 - Saitta, Lorenza
PB - IOS Press BV
T2 - 16th European Conference on Artificial Intelligence, ECAI 2004
Y2 - 22 August 2004 through 27 August 2004
ER -