Abstract
Qualitative spatial and temporal reasoning is based on so-called qualitative calculi. Algebraic properties of these calculi have several implications on reasoning algorithms. But what exactly is a qualitative calculus? And to which extent do the qualitative calculi proposed meet these demands? The literature provides various answers to the first question but only few facts about the second. In this paper we identify the minimal requirements to binary spatio-temporal calculi and we discuss the relevance of the according axioms for representation and reasoning. We also analyze existing qualitative calculi and provide a classification involving different notions of relation algebra.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Allen, J.F.: Maintaining knowledge about temporal intervals. Communications of the ACM 26(11), 832–843 (1983)
Balbiani, P., Condotta, J., Fariñas del Cerro, L.: Tractability results in the block algebra. J. Log. Comput. 12(5), 885–909 (2002)
Balbiani, P., Condotta, J., Ligozat, G.: On the consistency problem for the INDU calculus. J. Applied Logic 4(2), 119–140 (2006)
Cohn, A., Renz, J.: Qualitative spatial representation and reasoning. In: van Harmelen, F., Lifschitz, V., Porter, B. (eds.) Handbook of Knowledge Representation, ch. 13, pp. 551–596. Elsevier (2008)
Dechter, R.: Constraint processing. Elsevier Morgan Kaufmann (2003)
Düntsch, I.: Relation algebras and their application in temporal and spatial reasoning. Artif. Intell. Rev. 23(4), 315–357 (2005)
Dylla, F., Lee, J.H.: A combined calculus on orientation with composition based on geometric properties. In: ECAI 2010. pp. 1087–1088 (2010)
Dylla, F., Mossakowski, T., Schneider, T., Wolter, D.: Algebraic properties of qualitative spatio-temporal calculi. Tech. rep., University of Bremen, Cognitive Systems (2013), http://arxiv.org/abs/1305.7345
Egenhofer, M.: Reasoning about binary topological relations. In: Günther, O., Schek, H.-J. (eds.) SSD 1991. LNCS, vol. 525, pp. 143–160. Springer, Heidelberg (1991)
Frank, A.: Qualitative spatial reasoning with cardinal directions. In: Proc. of ÖGAI 1991. Informatik-Fachberichte, vol. 287, pp. 157–167. Springer (1991)
Gantner, Z., Westphal, M., Wölfl, S.: GQR - A Fast Reasoner for Binary Qualitative Constraint Calculi. In: Proc. of the AAAI 2008 Workshop on Spatial and Temporal Reasoning (2008)
Grigni, M., Papadias, D., Papadimitriou, C.H.: Topological inference. In: Proc. of IJCAI 1995 (1), pp. 901–907. Morgan Kaufmann (1995)
Hirsch, R., Hodkinson, I.: Relation algebras by games, Studies in logic and the foundations of mathematics, vol. 147. Elsevier (2002)
Isli, A., Cohn, A.: A new approach to cyclic ordering of 2D orientations using ternary relation algebras. Artif. Intell. 122(1-2), 137–187 (2000)
Jonsson, P., Drakengren, T.: A complete classification of tractability in RCC-5. J. Artif. Intell. Res (JAIR) 6, 211–221 (1997)
Kontchakov, R., Pratt-Hartmann, I., Wolter, F., Zakharyaschev, M.: Spatial logics with connectedness predicates. Log. Meth. Comp. Sci. 6(3) (2010)
Ligozat, G.: Reasoning about cardinal directions. J. Vis. Lang. Comput. 9(1), 23–44 (1998)
Ligozat, G.: Categorical methods in qualitative reasoning: The case for weak representations. In: Cohn, A.G., Mark, D.M. (eds.) COSIT 2005. LNCS, vol. 3693, pp. 265–282. Springer, Heidelberg (2005)
Ligozat, G.: Qualitative Spatial and Temporal Reasoning. Wiley (2011)
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)
Mackworth, A.K.: Consistency in networks of relations. Artif. Intell. 8, 99–118 (1977)
Maddux, R.: Relation algebras, Studies in logic and the foundations of mathematics, vol. 150. Elsevier (2006)
Moratz, R.: Representing Relative Direction as a Binary Relation of Oriented Points. In: Proc. of ECAI 2006. pp. 407–411. IOS Press (2006)
Moratz, R., Lücke, D., Mossakowski, T.: A condensed semantics for qualitative spatial reasoning about oriented straight line segments. Artif. Intell. 175, 2099–2127 (2011), http://dx.doi.org/10.1016/j.artint.2011.07.004
Moratz, R., Renz, J., Wolter, D.: Qualitative spatial reasoning about line segments. In: Proc. of ECAI 2000. pp. 234–238. IOS Press (2000)
Mossakowski, F.: Algebraische Eigenschaften qualitativer Constraint-Kalküle. Diplom thesis, Dept. of Comput. Science, University of Bremen (2007) (in German)
Mossakowski, T., Maeder, C., Lüttich, K.: The heterogeneous tool set, hets. In: Grumberg, O., Huth, M. (eds.) TACAS 2007. LNCS, vol. 4424, pp. 519–522. Springer, Heidelberg (2007)
Mossakowski, T., Moratz, R.: Qualitative reasoning about relative direction of oriented points. Artif. Intell. 180-181, 34–45 (2012), http://dx.doi.org/10.1016/j.artint.2011.10.003
Mossakowski, T., Lücke, D., Moratz, R.: Relations between spatial calculi about directions and orientations. Technical report, University of Bremen
Navarrete, I., Morales, A., Sciavicco, G., Cárdenas-Viedma, M.: Spatial reasoning with rectangular cardinal relations – the convex tractable subalgebra. Ann. Math. Artif. Intell. 67(1), 31–70 (2013)
Nebel, B., Scivos, A.: Formal properties of constraint calculi for qualitative spatial reasoning. KI 16(4), 14–18 (2002)
Pujari, A.K., Sattar, A.: A new framework for reasoning about points, intervals and durations. In: Proc. of IJCAI 1999. pp. 1259–1267 (1999)
Ragni, M., Scivos, A.: Dependency calculus: Reasoning in a general point relation algebra. In: Furbach, U. (ed.) KI 2005. LNCS (LNAI), vol. 3698, pp. 49–63. Springer, Heidelberg (2005)
Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and “Connection”. In: Proc. of KR 1992, pp. 165–176 (1992)
Renz, J.: Qualitative Spatial Reasoning with Topological Information. LNCS (LNAI), vol. 2293. Springer, Heidelberg (2002)
Renz, J., Mitra, D.: Qualitative direction calculi with arbitrary granularity. In: Zhang, C., Guesgen, H.W., Yeap, W.-K. (eds.) PRICAI 2004. LNCS (LNAI), vol. 3157, pp. 65–74. Springer, Heidelberg (2004)
Scivos, A.: Einführung in eine Theorie der ternären RST-Kalküle für qualitatives räumliches Schließen. Diplom thesis, University of Freiburg (2000) (in German)
Skiadopoulos, S., Koubarakis, M.: Composing cardinal direction relations. Artif. Intell. 152(2), 143–171 (2004)
Skiadopoulos, S., Koubarakis, M.: On the consistency of cardinal direction constraints. Artif. Intell. 163(1), 91–135 (2005)
Van de Weghe, N.: Representing and Reasoning about Moving Objects: A Qualitative Approach. Ph.D. thesis, Ghent University (2004)
Van de Weghe, N., Kuijpers, B., Bogaert, P., De Maeyer, P.: A qualitative trajectory calculus and the composition of its relations. In: Rodríguez, M.A., Cruz, I., Levashkin, S., Egenhofer, M. (eds.) GeoS 2005. LNCS, vol. 3799, pp. 60–76. Springer, Heidelberg (2005)
Vilain, M., Kautz, H., van Beek, P.: Constraint propagation algorithms for temporal reasoning: a revised report. In: Readings in Qualitative Reasoning about Physical Systems, pp. 373–381. Morgan Kaufmann (1989)
Wallgrün, J.O., Frommberger, L., Wolter, D., Dylla, F., Freksa, C.: Qualitative spatial representation and reasoning in the sparQ-toolbox. In: Barkowsky, T., Knauff, M., Ligozat, G., Montello, D.R. (eds.) Spatial Cognition 2007. LNCS (LNAI), vol. 4387, pp. 39–58. Springer, Heidelberg (2007)
Wallgrün, J.O., Frommberger, L., Dylla, F., Wolter, D.: SparQ User Manual V0.7. User manual, University of Bremen (January 2009)
Wallgrün, J.O., Wolter, D., Richter, K.F.: Qualitative matching of spatial information. In: Proceedings of ACM GIS (2010)
Wolter, D., Lee, J.H.: Qualitative reasoning with directional relations. Artificial Intelligence 174(18), 1498–1507 (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer International Publishing Switzerland
About this paper
Cite this paper
Dylla, F., Mossakowski, T., Schneider, T., Wolter, D. (2013). Algebraic Properties of Qualitative Spatio-temporal Calculi. In: Tenbrink, T., Stell, J., Galton, A., Wood, Z. (eds) Spatial Information Theory. COSIT 2013. Lecture Notes in Computer Science, vol 8116. Springer, Cham. https://doi.org/10.1007/978-3-319-01790-7_28
Download citation
DOI: https://doi.org/10.1007/978-3-319-01790-7_28
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-01789-1
Online ISBN: 978-3-319-01790-7
eBook Packages: Computer ScienceComputer Science (R0)