Customizing qualitative spatial and temporal calculi

Abstract

Qualitative spatial and temporal calculi are usually formulated on a particular level of granularity and with a particular domain of spatial or temporal entities. If the granularity or the domain of an existing calculus doesn't match the requirements of an application, it is either possible to express all information using the given calculus or to customize the calculus. In this paper we distinguish the possible ways of customizing a spatial and temporal calculus and analyze when and how computational properties can be inherited from the original calculus. We present different algorithms for customizing calculi and proof techniques for analyzing their computational properties. We demonstrate our algorithms and techniques on the Interval Algebra for which we obtain some interesting results and observations. We close our paper with results from an empirical analysis which shows that customizing a calculus can lead to a considerably better reasoning performance than using the non-customized calculus.