On Some Meta-Theoretic Topological Features of the Region Connection Calculus
Keywordsregion connection calculus, mereotopology, topology, mereology
This paper examines several intended topological features of the Region Connection Calculus (RCC) and argues that they are either underdetermined by the formal theory or given by the complement axiom. Conditions are identified under which the axioms of RCC are satisfied in topological models under various set restrictions. The results generalise previous results in the literature to non-strict topological models and across possible interpretations of connection. It is shown that the intended interpretation of connection and the alignment of self-connection with topological connection are underdetermined by the axioms of RCC, which suggests that additional axioms are necessary to secure these features. It is also argued that the complement axiom gives RCC models much of their topological structure. In particular, the incompatibility of RCC with interiors is argued to be given by the complement axiom.
Asher, N., and L. Vieu, “Toward a geometry of common sense: A semantics and a complete axiomatization of mereotopology”, Proceedings of the International Joint Conference on Artificial Intelligence, 1995.
Aurnague, M., and L. Vieu, “A three-level approach to the semantics of space”, pages 393–440 in C. Zelinsky-Wibbelt (ed.), The Semantics of Prepositions: From Mental Processing to Natural Language Processing, Berlin, Boston: Mouton de Gruyter, 1993. DOI: http://dx.doi.org/10.1515/9783110872576.393
Bennett, B., “Spatial reasoning with propositional logics”, Principles of Knowledge Representation and Reasoning: Proceedings of the Fourth International Conference, 1994: 51–62. DOI: http://dx.doi.org/10.1016/B978-1-4832-1452-8.50102-0
Bittner, T., and J. Stell, “A boundary-sensitive approach to qualitative location”, Annals of Mathematics and Artificial Intelligence, 24 (1998): 93–114. DOI: http://dx.doi.org/10.1023/A:1018945131135
Casati, R., and A. C. Varzi, Parts and Places: The Structures of Spatial Representations, Massachusetts: MIT Press, 1999.
Clarke, B. L., “A calculus of individuals based on ‘connection’ ”, Notre Dame Journal of Formal Logic, 22, 3 (1981): 204–218. DOI: http://dx.doi.org/10.1305/ndjfl/1093883455
Clarke, B. L., “Individuals and points”, Notre Dame Journal of Formal Logic, 26, 1 (1985): 61–75. DOI: http://dx.doi.org/10.1305/ndjfl/1093870761
Clementini, F., J. Sharma, and M. Egenhofer, “Modelling topological spatial relations: Strategies for query processing”, Computers and Graphics, 18, 6 (1994): 815–822. DOI: http://dx.doi.org/10.1016/0097-8493(94)90007-8
Cohn, A. G., “A hierarchical representation of qualitative shape based on connection and convexity”, pages 311–326 in A. Frank (ed.), International Conference on Spatial Information Theory, Springer Verlag, 1995. DOI: http://dx.doi.org/10.1007/3-540-60392-1_20
Cohn, A. G., “Calculi for qualitative spatial reasoning”, International Conference on Artificial Intelligence and Symbolic Mathematical Computing, 1996: 124–143. DOI: http://dx.doi.org/10.1007/3-540-61732-9_54"> http://dx.doi.org/10.1007/3-540-61732-9_54
Cohn, A. G., B. Bennett, J. Gooday, and N. M. Gotts, “Qualitative spatial representation and reasoning with the region connection calculus”, GeoInformatica, 1 (1997): 275–316. DOI: http://dx.doi.org/10.1023/A:1009712514511
Cohn, A. G., B. Bennett, J. Gooday, and N. M. Gotts, “Representing and reasoning with qualitative spatial relations about regions”, pages 97–134 in O. Stock (ed.), Spatial and Temporal Reasoning, Dordrecht: Springer, 1997. DOI: http://dx.doi.org/10.1007/978-0-585-28322-7_4
Cohn, A. G., and N. M. Gotts, “The ‘egg-yolk’ representation of regions with indeterminate boundaries”, pages 131–150 in C. Eschenbach, C. Habel, and B. Smith (eds.), Topological Foundations of Cognitive Science: Papers From the Workshop at the 1st International Summer Institute in Cognitive Science, 1994.
Cohn, A. G., D. A. Randell, and Z. Cui, “Taxonomies of logically defined qualitative spatial regions”, International Journal of Human Computer Studies, 43 (1995): 831–846. DOI: http://dx.doi.org/10.1006/ijhc.1995.1077
Cohn, A. G., D. A. Randell, Z. Cui, and B. Bennett, “Qualitative spatial reasoning and representation”, pages 513–522 in N. P. Carrete and M. G. Singh (eds.), Qualitative Reasoning and Decision Technologies, Barcelona: CIMNE, 1993.
Cui, Z., A. G. Cohn, and D. A. Randell, “Qualitative simulation based on a logical formalism of space and time”, Proceedings of the 10th National Conference on Artificial Intelligence, 1992: 679–684.
Cui, Z., A. G. Cohn, and D. A. Randell, “Qualitative and topological relationships in spatial databases”, pages 293–315 in D. Abel and B. C. Ooi (eds.), Advances in Spatial Databases, Vol. 692, Berlin: Springer Verlag, 1993. DOI: http://dx.doi.org/10.1007/3-540-56869-7_17
Dimov, G. and D. Vakarelov, “Contact algebras and region based theory of space: A proximity approach”, Fundamenta Informaticae, 74, 2–3 (2006): 209–249.
Dimov, G., and D. Vakarelov, “Contact algebras and region based theory of space: A proximity approach”, Fundamenta Informaticae, 74, 2–3 (2006): 251–282.
Düntsch, I., and M. Winter, “A representation theorem for Boolean contact algebras”, Theoretical Computer Science, 347 (2005): 498–512. DOI: http://dx.doi.org/10.1016/j.tcs.2005.06.030
Egenhofer, M., and D. Mark, “Naive geography”, pages 1–16 in A. U. Frank and W. Kuhn (eds.), Spatial Information Theory: A Theoretical Basis for GIS, Berlin: Springer-Verlag, 1995. DOI: http://dx.doi.org/10.1007/3-540-60392-1_1
Fujihara, H., and A. Mukerjee, “Qualitative reasoning about document design”, Technical report, Texas University, 1991.
Gooday, J. M., and A. G. Cohn, “Using spatial logic to describe visual languages”, Artificial intelligence Review, 10 (1996): 171–186. DOI: http://dx.doi.org/10.1007/BF00127678
Gotts, N. M, “How far can we ‘C’? Defining a ‘doughnut’ using connection alone”, Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference, 1994: 246–257. DOI: http://dx.doi.org/B978-1-4832-1452-8.50119-6
Gotts, N. M., “An axiomatic approach to topology for spatial information systems”, Technical report, University of Leeds, 1996.
Gotts, N. M., J. M. Gooday, and A. G. Cohn, “A connection based approach to common-sense topological description and reasoning”, The Monist, 79, 1 (1996): 51–75. DOI: http://dx.doi.org/10.5840/monist19967913
Kuipers, B. J., and T. S. Levitt, “Navigating and mapping in large-scale space”, AI Magazine, 9, 2 (1988): 25–43. DOI: http://dx.doi.org/10.1609/aimag.v9i2.674
Lehmann, F., and A. G. Cohn, “The EGG/YOLK reliability hierarchy: Semantic data integration using sorts with prototypes”, Proceedings of the Third International Conference on Information and Knowledge Management, 1994: 272–279. DOI: http://dx.doi.org/10.1145/191246.191293
Li, S., and M. Ying, “Region connection calculus: Its models and composition table”, Artificial Intelligence, 145 (2003): 121–146. DOI: http://dx.doi.org/10.1016/S0004-3702(02) 0372-7
Li, S., and M. Ying, “Generalized region connection calculus”, Artificial Intelligence, 160 (2004): 1–34. DOI: http://dx.doi.org/10.1016/j.artint.2004.05.012
Li, S., M. Ying, and Y. Li, “On countable RCC models”, Fundamenta Informaticae, 20 (2006): 1–23.
Liu, W., and S. Li, “On standard models of fuzzy region connection calculus”, International Journal of Approximate Reasoning, 52, 9 (2011): 1337–1354. DOI: http://dx.doi.org/10.1016/j.ijar.2011.07.001
Randell, D. A., and A. G. Cohn, “Modelling topological and metrical properties in physical processes”, International Conference on Principles of Knowledge Representation and Reasoning, 1989.
Randell, D. A., and A. G. Cohn, “Exploiting lattices in a theory of space and time”, Computers and Mathematics with Applications, 23 (1992): 459–476. DOI: http://dx.doi.org/10.1016/0898-1221(92)90118-2
Randell, D. A., Z. Cui, and A. G. Cohn, “A spatial logic based on regions and connection”, Proceedings of the Third International Conference on Principles of Knowledge Representation and Reasoning, 1992: 165–176.
Stell, J. G., “Boolean connection algebras: A new approach to the regionconnection calculus”, Artificial Intelligence, 122, 1–2 (2000): 111–136. DOI: http://dx.doi.org/10.1016/S0004-3702(00)00045-X
Stell, J. G., and M. F. Worboys, “The algebraic structure of sets of regions”, Spatial Information Theory: A Theoretical Basis for GIC, International Conference COSIT ’97, 1997: 163–174. DOI: http://dx.doi.org/10.1007/3-540-63623-4_49
Whitehead, A. N., Process and Reality, New York: Macmillan, 1929.
Winter, S., “Topology in raster and vector representation”, GeoInformatica, 4 (2000): 35–65. DOI: http://dx.doi.org/10.1023/A:1009828425380
Worboys, M., “Imprecision in finite resolution spatial data”, GeoInformatica, 2 (1998): 257–279. DOI: http://dx.doi.org/10.1023/A:1009769705164
Xia, L., and S. Li, “On minimal models of the region connection calculus”, Fundamenta Informaticae, 69, 4 (2006): 1–20.
How to Cite
Copyright (c) 2023 Nathaniel Gan
This work is licensed under a Creative Commons Attribution-NoDerivatives 4.0 International License.
Number of views and downloads: 624
Number of citations: 0