Publikation
A Categorical Perspective on Qualitative Constraint Calculi
Till Mossakowski; Lutz Schröder; Stefan Wölfl
In: Stefan Wölfl; Till Mossakowski (Hrsg.). Qualitative Constraint Calculi - Application and Integration. Workshop at KI 2006. Qualitative Constraint Calculi - Application and Integration. Workshop (KI-2006), located at 29th Annual German Conference on Artificial Intelligence, June 14-19, Bremen, Germany, Pages 28-39, 2006.
Zusammenfassung
In the domain of qualitative constraint reasoning, a subfield of AI which has evolved in the last 25 years, a large number of calculi for efficient reasoning about space and time has been developed. Reasoning problems in such calculi are usually formulated as constraint satisfaction problems. For temporal and spatial reasoning, these problems often have infinite domains, which need to be abstracted to (finite) algebras in order to become computationally feasible. Ligozat has argued that the notion of weak representation plays a crucial role: it not only captures the correspondence between abstract relations (in a relation algebra or non-associative algebra) and relations in a concrete domain, but also corresponds to algebraically closed constraint networks. In this work, we examine properties of the category of weak representations and treat the relations between partition schemes, non-associative algebras and concrete domains in a systematic way. This leads to the notion of semi-strong representation, which captures the correspondence between abstract and concrete relations better than the notion of weak representation does. The slogan is that semi-strong representations avoid unnecessary loss of information. Furthermore, we hope that the categorical perspective will help in the future to provide new insights on the important problem of determining whether algebraic closedness decides consistency of constraint networks.