Abstract
This paper argues for considering qualitative spatial and temporal reasoning in algebraic and category-theoretic terms. A central notion in this context is that of weak representation (WR) of the algebra governing the calculus. WRs are ubiquitous in qualitative reasoning, appearing both as domains of interpretation and as constraints. Defining the category of WRs allows us to express the basic notion of satisfiability (or consistency) in a simple way, and brings clarity to the study of various variants of consistency. The WRs of many popular calculi are of interest in themselves. Moreover, the classification of WRs leads to non-trivial model-theoretic results. The paper provides a not-too-technical introduction to these topics and illustrates it with simple examples.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Allen, J.F.: Maintaining knowledge about temporal intervals. Comm. of the ACM 26(11), 832–843 (1983)
Anger, F.D., Mitra, D., Rodriguez, R.V.: Temporal Constraint Networks in Nonlinear Time. In: Proc. of the ECAI 1998 Workshop on Spatial and Temporal Reasoning (W22), Brighton, UK, pp. 33–39 (1998)
Balbiani, P., Condotta, J.-F., Ligozat, G.: On the Consistency Problem for the INDU Calculus. In: Proceedings of TIME-ICTL-2003, Cairns, Australia (2003)
Broxvall, M., Jonsson, P.: Towards a complete classification of tractability in point algebras for nonlinear time. In: Jaffar, J. (ed.) CP 1999. LNCS, vol. 1713, pp. 129–143. Springer, Heidelberg (1999)
Condotta, J.-F., Tripakis, S., Ligozat, G.: Ultimately periodic qualitative constraint networks (2005)
Cristani, M.: The complexity of reasoning about spatial congruence. J. Artif. Intell. Res (JAIR) 11, 361–390 (1999)
Cristani, M., Hirsch, R.: The complexity of constraint satisfaction problems for small relation algebras. Artif. Intell. 156(2), 177–196 (2004)
Düntsch, I.: Relation algebras and their application in qualitative spatial reasoning. Technical Report CS-03-07, Brock University, St. Catarines, Ontario (2003)
Egenhofer, M., Rodríguez, A.: Relation algebras over containers and surfaces: An ontological study of a room space. Spatial Cognition and Computation 1, 155–180 (1999)
Gerevini, A., Nebel, B.: Qualitative spatio-temporal reasoning with RCC-8 and Allen’s interval calculus: Computational complexity. In: Proc. of ECAI 2002, pp. 312–316 (2002)
Hirsch, R., Hodkinson, I.: Relation Algebras by Games. In: Studies in Logic and the Foundations of Mathematics, vol. 147. North Holland, Amsterdam (2002)
Ladkin, P.B., Maddux, R.D.: On Binary Constraint Problems. Journal of the ACM 41(3), 435–469 (1994)
Ligozat, G.: Weak Representations of Interval Algebras. In: Proc. of AAAI 1990, pp. 715–720 (1990)
Ligozat, G.: On generalized interval calculi. In: Proc. of AAAI 1991, pp. 234–240 (1991)
Ligozat, G., Mitra, D., Condotta, J.-F.: Spatial and temporal reasoning: beyond Allen’s calculus. AI Communications 17(4), 223–233 (2004)
Ligozat, G., Renz, J.: What is a qualitative calculus? a general framework. In: Zhang, C., Guesgen, H.W., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 53–64. Springer, Heidelberg (2004)
Ligozat, G.: Reasoning about cardinal directions. Journal of Visual Languages and Computing 1(9), 23–44 (1998)
Ligozat, G.: Simple models for simple calculi. In: Freksa, C., Mark, D.M. (eds.) COSIT 1999. LNCS, vol. 1661, pp. 173–188. Springer, Heidelberg (1999)
Ligozat, G.: When Tables Tell It All: Qualitative Spatial and Temporal reasoning Based on Linear Orderings. In: Montello, D.R. (ed.) COSIT 2001. LNCS, vol. 2205, pp. 60–75. Springer, Heidelberg (2001)
Ligozat, G., Renz, J.: Problems with local consistency for Qualitative Calculi. In: Proceedings of ECAI 2004, Valencia, Spain, pp. 1047–1048 (2004)
Maddux, R.: Some varieties containing relation algebras. Trans. Amer. Math. Soc. 272(2), 501–526 (1982)
Pujari, A.K., Vijaya Kumari, G., Sattar, A.: INDU: An Interval and Duration Network. In: Australian Joint Conf. on Artificial Intelligence, pp. 291–303 (1999)
Randell, D., Cui, Z., Cohn, T.: A spatial logic based on regions and connection. In: Neumann, B. (ed.) Proc. of KR 1992, San Mateo, CA, pp. 165–176 (1992)
Renz, J.: A spatial odyssey of the interval algebra: 1. Directed intervals. In: IJCAI, pp. 51–56 (2001)
Tarski, A.: On the calculus of relations. Journal of Symbolic Logic 6, 73–89 (1941)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Ligozat, G. (2005). Categorical Methods in Qualitative Reasoning: The Case for Weak Representations. In: Cohn, A.G., Mark, D.M. (eds) Spatial Information Theory. COSIT 2005. Lecture Notes in Computer Science, vol 3693. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11556114_17
Download citation
DOI: https://doi.org/10.1007/11556114_17
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28964-7
Online ISBN: 978-3-540-32020-3
eBook Packages: Computer ScienceComputer Science (R0)