| Publication type: |
Article in Proceedings |
| Author: |
Till Mossakowski, Lutz Schröder, Stefan Wölfl |
| Editor: |
Stefan Wölfl, Till Mossakowski |
| Title: |
A Categorical Perspective on Qualitative Constraint Calculi |
| Book / Collection title: |
Qualitative Constraint Calculi - Application and Integration. Workshop at KI 2006 |
| Page(s): |
28 – 39 |
| Year published: |
2006 |
| Abstract: |
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. |
| PDF Version: |
http://www.informatik.uni-bremen.de/~till/papers/qcc-cat.pdf |
| PostScript Version: |
http://www.informatik.uni-bremen.de/~till/papers/qcc-cat.ps |
| Status: |
Reviewed |
| Last updated: |
05. 06. 2006 |
|
 |
