On countable RCC models

• Autorzy: Li S. , Ying M. , Li Y.
• Języki publikacji: EN

Abstrakty

EN

Region Connection Calculus (RCC) is the most widely studied formalism of Qualitative Spatial Reasoning. It has been known for some time that each connected regular topological space provides an RCC model. These `standard' models are inevitable uncountable and regions there cannot be represented finitely. This paper, however, draws researchers' attention to RCC models that can be constructed from finite models hierarchically. Compared with those `standard' models, these countable models have the nice property that regions where can be constructed in finite steps from basic ones. We first investigate properties of three countable models introduced by Düntsch, Stell, Li and Ying, resp. In particular, we show that (i) the contact relation algebra of our minimal model is not atomic complete; and (ii) these three models are non-isomorphic. Second, for each n > 0, we construct a countable RCC model that is a sub-model of the standard model over the Euclidean unit n-cube; and show that all these countable models are non-isomorphic. Third, we show that every finite model can be isomorphically embedded in any RCC model. This leads to a simple proof for the result that each consistent spatial network has a realization in any RCC model.

Słowa kluczowe

EN

Region Connection Calculus; qualitative spatial reasoning (QSR); generalized Boolean connection algebra; countable RCC models; hierarchical spatial reasoning

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 65, nr 4
• Strony: 329--351
• Opis fizyczny: Bibliogr. 31 poz.

Twórcy

autor

Li S.

• State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

autor

Ying M.

• State Key Laboratory of Intelligent Technology and Systems, Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China

autor

Li Y.

• Department of Mathematics, Shaanxi Normal University, Xi’an 710062, China

Bibliografia

• [1] Asher, N., Vieu, L.: Toward a Geometry of Common Sense: A Semantics and a Complete Axiomatization of Mereotopology, Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI-95) (C. Mellish, Ed.), Montreal, 1995, 846–852.
• [2] Bell, J., Machover,M.: A Course in Mathematical Logic, North-Holland, 1977.
• [3] Bennett, B.: Spatial Reasoning with Propositional Logics, Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference (KR94) (J. Doyle, E. Sandewall, P. Torasso, Eds.), Morgan Kaufmann, San Francisco, CA., 1994.
• [4] Bennett, B.: Modal Logics for Qualitative Spatial Reasoning, Bulletin of the Interest Group in Pure and Applied Logic (IGPL), 4(1), 1996, 23–45.
• [5] Bennett, B.: Logical Representations for Automated Reasoning about Spatial Relationships, Ph.D. Thesis, School of Computer Studies, University of Leeds, 1997.
• [6] Bittner, T., Stell, J.: A boundary-sensetive approach to qualitative location, Annals of Mathematics and Artificial Intelligence, 24, 1998, 93–114.
• [7] Clarke, B.: A calculus of individuals based on ‘connection’, Notre Dame Journal of Formal Logic, 22, 1981, 204–218.
• [8] Clarke, B.: Individuals and Points, Notre Dame Journal of Formal Logic, 26(1), 1985, 61–75.
• [9] Clementini, E., Sharma, J., Egenhofer, M.: Modeling topological spatial relations: strategies for query processing, Computers and Graphics, 18, 1994, 815–822.
• [10] Cohn, A., Bennett, B., Gooday, J., Gotts, N.: Qualitative Spatial Representation and Reasoning with the Region Connection Calculus, GeoInformatica, 1, 1997, 275–316.
• [11] Cohn, A., Hazarika, S.: Qualitative spatial representation and reasoning: An overview, Fundamenta Informaticae, 46, 2001, 2–32.
• [12] Cui, Z., Cohn, A., Randell, D.: Qualitative and Topological Relationships in Spatial Databases, in: Advances in Spatial Databases, Lecture Notes in Computer Sciences 692 (D. Abel, B. Ooi, Eds.), Springer Verlag, Berlin, 1993, 293–315.
• [13] Düntsch, I.: Relation algebras and their application in qualitative spatial reasoning, 2003, Preprint.
• [14] Düntsch, I., Schmidt, G., Winter, M.: A necessary relation algebra for mereotopology, Studia Logica, 69, 2001, 381–409.
• [15] Düntsch, I., Wang, H., McCloskey, S.: Relation algebras in qualitative spatial reasoning, Fundamenta Informaticae, 39, 1999, 229–248.
• [16] Düntsch, I., Wang, H., McCloskey, S.: A relation-algebraic approach to the Region Connection Calculus, Theoretical Computer Scinece, 255, 2001, 63–83.
• [17] Galton, A.: The mereotopology of discrete space, Spatial Information Theory. Cognitive and Computational Foundations of Geographic Information Science, International Conference COSIT’99 (C. Freksa, D. Mark, Eds.), Springer, Berlin, 1999, 251–266.
• [18] Gotts, N.: An axiomatic approach to spatial information systems, Research Report 96.25, School of Computer Studies, University of Leeds, 1996.
• [19] Li, S., Ying, M.: Generalized Region Connection Calculus, Artificial Intelligence, In press.
• [20] Li, S., Ying, M.: Extensionality of the RCC8 composition table, Fundamenta Informaticae, 55(3-4), 2003, 363–385.
• [21] Li, S., Ying, M.: Region Connection Calculus: Its models and composition table, Artificial Intelligence, 145(1-2), 2003, 121–146.
• [22] Nebel, B.: Computational properties of qualitative spatial reasoning: First results, KI-95: Advances in Artificial Intelligence, Proceedings of the 19th Annual German Conference on Artificial Intelligence, Springer-Verlag, Berlin, Germany, 1995, 233–244.
• [23] Randell, D., Cohn, A.: Modelling topological and metrical properties of physical processes, First International Conference on the Principles of Knowledge Representation and Reasoning (R. Brachman, H. Levesque, R. Reiter, Eds.), Morgan Kaufmann, Los Altos, 1989, 55–66.
• [24] Randell, D., Cui, Z., Cohn, A.: A spatial logic based on regions and connection, Proceedings of the 3rd International Conference on Knowledge Representation and Reasoning (B. Nebel, W. Swartout, C. Rich, Eds.), Morgan Kaufmann, Los Allos, 1992, 165–176.
• [25] Renz, J.: A canonical model of the Region Connection Calculus, Proceedings of the 6th International Conference on Knowledge Representation and Reasoning, Morgan Kaufmann, 1998, 330–341.
• [26] Renz, J.: Qualitative spatial reasoning with topological information, vol. 2293 of Lecture Notes in Artificial Intelligence, Springer-Verlag, Berlin, Germany, 2002.
• [27] Renz, J., Nebel, B.: On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus, Artificial Intelligence, 108, 1999, 69–123.
• [28] Stell, J.: Boolean connection algebras: A new approach to the Region-Connection Calculus, Artificial Intelligence, 122, 2000, 111–136.
• [29] Winter, S.: Topological relations in hierarchial partitions, Spatial Information Theory. Cognitive and Computational Foundations of Geographic information Science, International Conference COSIT’99 (C. Freksa, D. Mark, Eds.), Springer, Berlin, 1999, 141–155.
• [30] Winter, S.: Topology in raster and vector representation, GeoInformatica, 4, 2000, 35–65.
• [31] Worboys, M.: Imprecision in finite resolution spatial data, GeoInfomatica, 2, 1998, 257–279