Relation Algebras with Preferences

Alexander Scivos

Relation algebras are a well-established formalism for qualitative reasoning. In a relation algebra, knowledge about relations between entities such as points, areas, or intervals is formally concluded, even under uncertainty of the relation. Then, unions of relations are used in which all relations have equal rank. However, this is not the way humans think. In case of uncertainty, we humans usually prefer some possible relations over others. In the talk, a formalization of this preference will be presented and formal criteria will be developed. With this formalization, the mental model preference can be applied in traditional reasoning algorithms, like Montari's path consistency algorithm. Moreover, it can be used as a heuristic for the backtracking procedure in CSPs over relation algebras that are known to be NPhard.