Problems with local consistency for qualitative calculi

Gerard Ligozat, Jochen Renz

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

2 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationECAI 2004 - 16th European Conference on Artificial Intelligence, including Prestigious Applications of Intelligent Systems, PAIS 2004 - Proceedings
EditorsRamon Lopez de Mantaras, Lorenza Saitta
PublisherIOS Press BV
Pages1047-1048
Number of pages2
ISBN (Electronic)9781586034528
Publication statusPublished - 2004
Externally publishedYes
Event16th European Conference on Artificial Intelligence, ECAI 2004 - Valencia, Spain
Duration: 22 Aug 200427 Aug 2004

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume110
ISSN (Print)0922-6389
ISSN (Electronic)1879-8314

Conference

Conference16th European Conference on Artificial Intelligence, ECAI 2004
Country/TerritorySpain
CityValencia
Period22/08/0427/08/04

Fingerprint

Dive into the research topics of 'Problems with local consistency for qualitative calculi'. Together they form a unique fingerprint.

Cite this