On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi

讲座内容：Qualitative calculi play a central role in representing and reasoning about qualitative spatial and temporal knowledge. This talk introduces and discusses distributive subalgebras of qualitative calculi, which are subalgebras in which (weak) composition distributives overnonempty intersections.

We show for several most popular qualitative calculi that path consistent constraint networks over a distributive subalgebra are always minimal and strongly n-consistent (in a qualitative sense).Moreover, we give a characterisation of distributive subalgebras, which states that the intersection of a set of m ≥ 3 relations in the subalgebra is nonempty if and only if the intersection of every two of these relations is nonempty. We further compute and generate all maximal distributive subalgebras for those qualitative calculi. Lastly, we establish two nice properties which will playan important role in efficient reasoning with constraint networks involving alarge number of variables.

This talk is based on the following publications:

[1] Zhiguo Long, Sanjiang Li. On Distributive Subalgebras of Qualitative Spatial and Temporal Calculi, Proceedings of the Twelfth Conference on Spatial Information Theory (COSIT 2015), Santa Fe, New Mexico, USA, October 12-16, 2015.

[2] Sanjiang Li, Zhiguo Long, Weiming Liu, Matt Duckham, and Alan Both. On Redundant Topological Constraints. Artificial Intelligence, 2015, 225: 51-78.