by Till Mossakowski, Lutz Schröder and Stefan Wölfl
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.
Reference:
Till Mossakowski, Lutz Schröder and Stefan Wölfl: A Categorical Perspective on Qualitative Constraint Calculi, In Stefan Wölfl, Till Mossakowski, eds.: Qualitative Constraint Calculi - Application and Integration. Workshop at KI 2006, pp. 28–39, 2006. [preprint]
Bibtex Entry:
@InProceedings{Mossakowski06EtAl,
author = {Till Mossakowski and Lutz Schr{\"o}der and Stefan W{\"o}lfl},
title = {A Categorical Perspective on Qualitative Constraint Calculi},
year = {2006},
editor = {Stefan W{\"o}lfl and Till Mossakowski},
booktitle = {Qualitative Constraint Calculi - Application and Integration. Workshop at KI 2006},
pages = {28--39},
comment = { <a href = "http://www.informatik.uni-bremen.de/~till/papers/qcc-cat.pdf"> [preprint] </a>},
psurl = {http://www.informatik.uni-bremen.de/~till/papers/qcc-cat.ps},
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.},
}