×

The Galois lattice as a hierarchical structure for topological relations. (English) Zbl 1125.06005

Summary: This paper presents the construction and the comparison of Galois lattices of topological relations for qualitative spatial representation and reasoning. The lattices rely on a correspondence between computational operations working on quantitative data, on the one hand, and topological relations working on qualitative knowledge units, on the other hand. After introducing the context of the present research work, i.e., the RCC-8 model of topological relations, we present computational operations for checking topological relations on spatial regions. From these operations two sets of computational conditions are derived that can be associated to topological relations through a Galois connection. The associated Galois lattices are presented and compared. Elements of the practical use of the lattices for representing spatial knowledge and for reasoning are also introduced and discussed.

MSC:

06A15 Galois correspondences, closure operators (in relation to ordered sets)
06B99 Lattices
68T30 Knowledge representation
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)

Software:

YAFOOL
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Le Ber, F., Mangelinck, L.: A formal representation of landscape spatial patterns to analyze satellite images. AI Appl. (Natural Resources, Agriculture, and Environmental Science) 12 (1–3), 51–59 (1998)
[2] Barbut, M., Monjardet, B.: Ordre et classification – Algèbre et combinatoire, Hachette, Paris (1970) · Zbl 0267.06001
[3] Davey, B., Priestley, H.: Introduction to Lattices and Order. Cambridge University Press, Cambridge, UK (1990) · Zbl 0701.06001
[4] Ganter, B., Wille, R.: Formal Concept Analysis. Springer, Berlin (1999) · Zbl 0909.06001
[5] Egenhofer, M.J., Franzosa, R.D.: Point-set topological spatial relations. Int. J. Geog. Inf. Syst. 5(2), 161–174 (1991)
[6] Egenhofer, M.J., Sharma, J.: Topological relations between regions in \(\mathbb{R}^{2} \) and \(\mathbb{Z}^{2} \) . In: Abel, D.J., Ooi, B.C. (eds.) Advances in Spatial Databases, Third International Symposium, SSD’93, Singapore, LNCS 692, pp. 316–336. Springer, Berlin Heidelberg New York (1993)
[7] Bennett, B., Isli, A., Cohn, A.G.: A system handling RCC-8 queries on 2D regions representable in the closure algebra of half-planes. In: Proceedings of the 11th International Conference on Industrial and Engineering Applications of Artificial Intelligence and Expert Systems (IEA-AIE), LNCS 1415, pp. 281–290. Springer, Berlin Heidelberg New York (1998)
[8] Randell, D.A., Cohn, A.G.: Exploiting lattices in a theory of space and time. Comput. Math. Appl. 23(6–9), 459–476 (1992) · Zbl 0794.68147
[9] Bennett, B.: Spatial reasoning with propositional logics. In: Doyle, J., Sandwall, E., Torasso, P. (eds.) Proceeding of the Fourth International Conference on Principles of Knowledge Representation and Reasoning (KR’94), pp. 246–257. Morgan Kaufmann, San Mateo, CA (1994)
[10] Möller, R., Wessel, M.: Terminological Default Reasoning about spatial information: A First Step. In: Freksa, C., Mark, D.M. (eds.) Spatial Information Theory, Cognitive and Computational Foundations of Geographic Information Science, LNCS 1661, Springer, 1999, International Conference COSIT’99, pp. 189–204. Stade, Germany (1999)
[11] Kainz, W., Egenhofer, M.J., Greasley, I.: Modelling spatial relations and operations with partially ordered sets. Int. J. Geogr. Inf. Syst. 7(3), 215–229 (1993)
[12] Le Ber, F., Napoli, A.: The design of an object-based system for representing and classifying spatial structures and relations. J. Univers. Comput. Sci. 8(8), 751–773 (2002)
[13] Vieu, L.: Spatial representation and reasoning in artificial intelligence. In: Stock, O. (ed.) Spatial and Temporal Reasoning, pp. 5–42. Kluwer, Boston (1997)
[14] Randell, D.A., Cui, Z., Cohn, A.G.: A spatial logic based on regions and connection. In: 3rd International Conference on Principles of Knowledge Representation and Reasoning, pp. 165–176. Morgan Kaufmann, San Mateo, CA (1992)
[15] Cohn, A.G., Bennett, B., Gooday, J., Gotts, N.M.: Representing and reasoning with qualitative spatial relations about regions. In: Stock, O. (ed.) Spatial and Temporal Reasoning, pp. 97–134. Kluwer, Boston (1997)
[16] Clarke, B.L.: A calculus of individuals based on ’connection’. Notre Dame J. Form. Log. 22(3), 204–218 (1981) · Zbl 0476.03035
[17] Randell, D.A., Cohn, A.G., Cui, Z.: Computing transitivity tables: a challenge for automated theorem provers. In: Proceedings of the 11th international conference on automated deduction, CADE’92, LNCS 607, pp. 786–790. Springer, Berlin Heidelberg New York (1992)
[18] Cohn, A.G., Randell, D.A., Cui, Z., Bennet, B.: Qualitative spatial reasoning and representation. In: Piera Carrete, N., Singh, M.G. (eds.) IMACS Int. Workshop on Qualitative Reasoning and Decision Technologies, pp. 513–522. Barcelona, Spain (1993)
[19] Randell, D., Witkowski, M.: Building large composition tables via axiomatic theories. In: Proceedings of the Eighth International Conference on Principles of Knowledge Representation and Reasoning (KR2002), Toulouse, France, pp. 26–35. Morgan Kaufmann, San Mateo, CA (2002)
[20] Le Ber, F., Napoli, A.: Design and comparison of lattices of topological relations for spatial representation and reasoning. J. Exp. Theor. Artif. Intell. 15(3), 331–371 (2003) · Zbl 1066.68126
[21] Egenhofer, M.J.: A formal definition of binary topological relationships. In: Litwin, W., Schek, H. (eds.) Foundations of Data Organization and Algorithms, FODO 1989, Paris, France, LNCS 367, pp. 457–472. Springer, Berlin Heidelberg New York (1989)
[22] Mangelinck, L.: Représentation et classification de structures spatiales. Application à la reconnaissance de paysages agricoles, Thèse de doctorat, Université Henri Poincaré Nancy 1 (1998)
[23] Le Ber, F., Mangelinck, L., Napoli, A.: Design and comparison of lattices of topological relations for spatial representation and reasoning. Rapport de recherche INRIA RR-4321, 57 (2001)
[24] Duquenne, V.: Latticial structures in data analysis. Theor. Comp. Sci. 217, 407–436 (1999) · Zbl 1034.68510
[25] Guigues, J.-L., Duquenne, V.: Familles minimales d’implications informatives résultant d’un tableau de données binaires. Math. Sci. Hum. 95, 5–18 (1986)
[26] Duquenne, V.: Contextual implications between attributes and some representational properties for finite lattices. In: Beiträge zur Begriffsanalyse, pp. 213–239. B.I. Wissenschafts-verlag, Mannheim (1987)
[27] Wille, R.: Concept lattices and conceptual knowledge systems. Comput. Math. Appl. 23(6–9), 493–515 (1992) · Zbl 0766.68129
[28] Ducournau, R.: Y3 : YAFOOL, the object oriented language, SEMA Group (1991)
[29] Ligozat, G.: Simple models for simple calculi. In: Freksa, C., Mark, D.M. (eds.) Spatial Information Theory, Cognitive and Computational Foundations of Geographic Information Science, LNCS 1661, Springer, 1999, International Conference COSIT’99, pp. 173–188. Stade, Germany (1999)
[30] Godin, R., Missaoui, R.: An incremental concept formation approach for learning from databases. Theor. Comp. Sci. 133(2), 387–419 (1994) · Zbl 0938.68806
[31] Simon, A., Napoli, A.: Building viewpoints in an object-based representation system for knowledge discovery in databases. In: Rubin, S. (ed.) Proceedings of the first international conference on information reuse and integration (IRI’99), pp. 104–108. Atlanta, Geogia, ISCA (1999)
[32] Valtchev, P., Missaoui, R., Godin, R.: Formal concept analysis for knowledge discovery and data mining: The new challenges. In: Eklund, P.W. (ed.) Concept Lattices, Second International Conference on Formal Concept Analysis, ICFCA 2004, Sydney, Australia, Springer. Lect. Notes Comput. Sci. 2961, 352–371 (2004) · Zbl 1198.68246
[33] Price, K., Russ, T., MacGregor, R.: Knowledge representation for computer vision: the VEIL Project. In: ARPA Image Understanding Workshop (1994)
[34] Russ, T., MacGregor, R., Salemi, B., Price, K., Nevatia, R.: VEIL: combining semantic knowledge with image understanding. In: ARPA Image Understanding Workshop (1996)
[35] MacGregor, R.M.: Inside the LOOM Description Classifier. ACM Sigart Bulletin 2(3), 88–92 (1991)
[36] MacGregor, R., Brill, D.: Recognition algorithms for the Loom classifier. In: Proceedings of AAAI’92, pp. 774–779. San Jose, USA (1992)
[37] Haarslev, V., Lutz, C., Möller, R.: A description logic with concrete domains and a role-forming predicate operator. J. Log. Comput. 9(3), 351–384 (1999) · Zbl 0940.03037
[38] Le Ber, F., Napoli, A., Metzger, J.-L., Lardon, S.: Modeling and comparing farm maps using graphs and case-based reasoning. J. Univers. Comput. Sci. 9(9), 1073–1095 (2003)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.