Extensionality of the RCC8 Composition Table

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

Abstrakty

EN

This paper is mainly concerned with the RCC8 composition table entailed by the Region Connection Calculus (RCC), a well-known formalism for Qualitative Spatial Reasoning. This table has been independently generated by Egenhofer in the context of Geographic Information Systems. It has been known for some time that the table is not extensional for each RCC model. This paper however shows that the Egenhofer model is indeed an extensional one for the RCC8 composition table. Moreover this model is the maximal extensional one for the RCC8 composition table in a sense.

Słowa kluczowe

EN

Region Connection Calculus; qualitative spatial reasoning (QSR); weak composition; composition table; RCC8 relations; extensionality

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2003
• Tom: Vol. 55, nr 3,4
• Strony: 363--385
• Opis fizyczny: bibliogr. 38 poz.

Twórcy

autor

Li S.

autor

Ying M.

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

Bibliografia

• [1] Allen, J. F.: Maintaining knowledge about temporal intervals, Communications of the ACM, 26, 1983, 832-843.
• [2] Armstrong, M. A.: Basic Topology, Springer-Verlag, New York, 1983.
• [3] Asher, N., Vieu, L.: Toward a geometry of common sense: a semantics and a complete axiomatization of mereotopology, in:IJCAI 95, Proceedings of the 14th International Joint Conference on Artificial Intellegence (C. Mellish Ed.), 1995, 846-852.
• [4] Bennett, B.: Some observations and puzzles about composing spatial and temporal relations, in: Proceedings ECAI-94 Workshop on Spatial and Temporal Reasoning (R. Rodr´ıguez Ed.), 1994.
• [5] Bennett, B.: Spatial reasoning with propositional logics, in: Principles of Knowledge Representation and Reasoning: Proceedings of the 4th International Conference (KR94) (J. Doyle, E. Sandewall and P. Torasso Eds.), Morgan Kaufmann, 1994.
• [6] Bennett, B.: Logical Representations for Automated Reasoning about Spatial Relationships, PhD thesis, University of Leeds, UK, 1998.
• [7] Bennett, B.: A categorical axiomatisation of region-based geometry, Fundamenta Informaticae, 46, 2001, 145-158.
• [8] Bennett, B., Isli, A., Cohn, A. G.: When does a composition table provide a complete and tractable proof procedure for a relational constraint language? Proceedings of the IJCAI-97 workshop on Spatial and Temporal Reasoning, Nagoya, Japan, 1997.
• [9] Bittner, T., Stell, J. G.: A boundary-sensetive approach to qualitative location, Ann. Math. Artificial Intelligence 24, 1998, 93-114.
• [10] Clementini, E., Sharma, J., Egenhofer, M. J.: Modeling topological spatial regions: strategies for query processing, Comput. Graph, 18, 1994, 815-822.
• [11] Cui, Z., Cohn, A. G., Randell, D. A.: Qualitative and topological relationships in spatial databases, in: Advances in Spatial Databases (D. Abel and B. C. Ooi Eds.), LNCS 692, Springer-Verlag, Berlin, 1993,
• 293-315.
• [12] Düntsch, I.: A tutorial on relation algebras and their application in spatial reasoning, Given at OSIT, August 1999. Available via http://www.infj.ulst.ac.uk/ cccz23/.
• [13] Düntsch, I., Schmidt, G., Winter, M.: A necessary relation algebra for mereotopology, Studia Logica, 69, 2001, 380-409.
• [14] Düntsch, I., Wang, H., McCloskey, S.: Relation algebras in qualitative spatial reasoning, Fundamenta Informaticae, 39, 1999, 229-248.
• [15] Düntsch, I., Wang, H., McCloskey, S.: A relation-algebraic approach to the region connection calculus, Theoretical Computer Scinece, 255, 2001, 63-83.
• [16] Egenhofer, M. J.: Reasoning about binary topological relations, in: Advances in Spatial Databases (O. Günther, H. J. Schek Eds.), LNCS 525, Springer, New York, 1991, 143-160.
• [17] Egenhofer, M. J., Clementini, E., Di Felice, P.: Topological relationships between regions with holes, International Journal of Geographical Information Systems, 8, 1994, 129-142.
• [18] Egenhofer, M. J., Franzosa, R.: Point-set topological spatial relations, International Journal of Geographical Information Systems, 5, 1991, 161-174.
• [19] Engelking, R.: General Topology, Polish Scientific Publishers, Warszawa, 1977.
• [20] Galton, A.: Modes of overlap, J. Visual Languages and Computing, 9, 1998, 61-79.
• [21] Gotts, N. M.: An axiomatic approach to spatial information systems, Research Report 96.25, University of Leeds, School of Computer Studies, 1996.
• [22] Grigni, M., Papadias, D., Papadimitriou, C.: Topological inference, in: IJCAI-95, Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (C. Mellish Ed.), Morgan Kaufmann Publishers, San Mateo, CA, USA., 1995, 901-906.
• [23] Kelly, J. L.: General Topology, Springer-Verlag, New York, 1975.
• [24] Knauff, M., Rauh, R., Renz, J.: A cognitive assessment of topological spatial relations: results from an empirical investigation, in: Spatial Information Theory, A Theoretical Basis for GIS, International Conference COSIT ’97 Proceedings, Springer-Verlag, Berlin, Germany, 1997, 193-206.
• [25] Li, S., Ying, M.: Generalized Region Connection Calculus, submitted.
• [26] Li, S., Ying, M.: Region Connection Calculus: Its models and composition table, Artificial Intelligence, 145(1-2), 2003, 121-146.
• [27] Li, Y., Li, S., Ying, M.: Relational reasoning in the Region Connection Calculus, submitted.
• [28] Nebel, B.: Computational properties of qualitative spatial reasoning: First results, in: KI-95: Advances in Artificial Intelligence, Proceedings of the 19th Annual German Conference on Artificial Intelligence, Springer-Verlag, Berlin, Germany, 1995, 233-244.
• [29] Pratt, I., Schoop, D.: A complete axiom system for polygonal mereotopology of the real plane, Journal of Philosophical Logic, 27, 1998, 621-658.
• [30] Randell, D. A., Cui, Z., Cohn, A. G.: A spatial logic based on regions and connection, in: Proceedings of the 3rd International Conf Knowledge Representation and Reasoning (B. Nebel, W. Swartout, C. Rich Eds.), Morgan Kaufmann, Los Allos, CA., 1992, 165-176.
• [31] 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.
• [32] 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.
• [33] Renz, J.: Qualitative spatial reasoning with topological information, LNAI 2293, Springer-Verlag, Berlin, Germany, 2002.
• [34] Smith, T. R., Park, K. K.: Algebraic approach to spatial reasoning, International Journal of Geographical Information Systems, 6, 1992, 177-192.
• [35] Stell, J. G.: Boolean connection algebras: A new approach to the Region-Connection Calculus, Artificial Intelligence, 122, 2000, 111-136.
• [36] Wolter, F., Zakharyaschev, M.: Spatial-temporal representation and reasoning based on RCC-8, in: Proceedings of KR2000 Conferences, 2000, 3-14.
• [37] Worboys, M.: Imprecision in finite resolution spatial data, GeoInfomatica, 2, 1998, 257-279.
• [38] Worboys, M., Bofakos, P.: A canonical model for a class of areal spatial objects, in: Third international Symposium on Large Spatial Databases (D. Abel, B.C. Ooi Eds.), LNCS 692, Springer-verlag, New York, 1993, 36-52.