Abstract
The main conceptual contribution in this paper is to present an approach to knowledge representation and reasonings based on labeled graphs and labeled graph homomorphism. Strengths and weaknesses of this graph-based approach are discussed. Main technical contributions are the followings. Fundamental results about the kernel of this approach, the so-called simple graphs model are synthesized. It is then shown that the basic deduction problem on simple graphs is essentially the same problem as conjunctive query containment in databases and constraint satisfaction; polynomial parcimonious transformations between these problems are exhibited. Grounded on the simple graphs model, a knowledge representation and reasoning model allowing to deal with facts, production rules, transformation rules, and constraints is presented, as an illustration of the graph-based approach.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison- Wesley, Reading (1995)
Baget, J.-F.: A simulation of co-identity with rules in simple and nested graphs. In: Tepfenhart, W.M. (ed.) ICCS 1999. LNCS (LNAI), vol. 1640, pp. 442–455. Springer, Heidelberg (1999)
Bos, C., Botella, B., Vanheeghe, P.: Modeling and simulating human behaviors with conceptual graphs. In: Delugach, H.S., Keeler, M.A., Searle, L., Lukose, D., Sowa, J.F. (eds.) ICCS 1997. LNCS (LNAI), vol. 1257, pp. 275–289. Springer, Heidelberg (1997)
Baget, J.-F., Genest, D., Mugnier, M.-L.: Knowledge acquisition with a pure graph-based knoweldge representation model — application to the sisyphus-i case study. In: Proc. KAW 1999 (1999)
Baader, F., Molitor, R., Tobies, S.: Tractable and Decidable Fragments of Conceptual Graphs. In: Tepfenhart, W.M. (ed.) ICCS 1999. LNCS (LNAI), vol. 1640, pp. 480–493. Springer, Heidelberg (1999)
Chein, M., Mugnier, M.L.: Graphs: Fundamental Notions. Revue d’Intelligence Artificielle 6(4), 365–406 (1992)
Chein, M., Mugnier, M.L.: Conceptual Graphs are also Graphs. Research Report 95-004, LIRMM, p. 17 (January 1995)
Chein, M., Mugnier, M.-L., Simonet, G.: Nested Graphs: a Graph-based Knowledge Representation Model with FOL semantics. In: Proc. KR 1998, pp. 524–534. Morgan Kaufmann, San Francisco (1998)
Coulondre, S., Salvat, E.: Piece Resolution: Towards Larger Perspectives. In: Mugnier, M.-L., Chein, M. (eds.) ICCS 1998. LNCS (LNAI), vol. 1453, pp. 179–193. Springer, Heidelberg (1998)
Gaines, B.R., Shaw, M.L.: Knowledge and requirements engineering. In: Proc. KAW 1995 (1995)
Ghosh, B.C., Wuwongse, V.: A direct Proof Procedure for Definite Conceptual Graph programs. In: Ellis, G., Rich, W., Levinson, R., Sowa, J.F. (eds.) ICCS 1995. LNCS, vol. 954, pp. 158–172. Springer, Heidelberg (1995)
Jackman, M.K.: Inference and the Conceptual Graph Knowledge Representation Language. In: Moralee, S. (ed.) Research and Development in Expert Systems IV. Cambridge University Press, Cambridge (1988)
Kerdiles, G., Salvat, E.: A sound and complete proof procedure based on tableaux and projection. In: Delugach, H.S., Keeler, M.A., Searle, L., Lukose, D., Sowa, J.F. (eds.) ICCS 1997. LNCS (LNAI), vol. 1257, pp. 371–385. Springer, Heidelberg (1997)
Kolaitis, P.G., Vardi, M.Y.: Conjunctive-Query Containment and Constraint Satisfaction. In: Proceedings of PODS 1998 (1998)
Mugnier, M.L., Chein, M.: Characterization and Algorithmic Recognition of Canonical Conceptual Graphs. In: Mineau, G.W., Sowa, J.F., Moulin, B. (eds.) ICCS 1993. LNCS (LNAI), vol. 699, pp. 294–311. Springer, Heidelberg (1993)
Mugnier, M.L., Chein, M.: Représenter des connaissances et raisonner avec des graphes. Revue d’Intelligence Artificielle 10(1), 7–56 (1996)
Mugnier, M.L.: On generalization/specialization for conceptual graphs. J. Expt. Theor. Artif. Intell. 7(3), 325–344 (1995)
Preller, A., Mugnier, M.-L., Chein, M.: Logic for Nested Graphs. Computational Intelligence 14(3) (1998)
Simonet, G., Chein, M., Mugnier, M.-L.: Projection in Conceptual Graphs and Query Containment in nr-Datalog. R.R. LIRMM (1998)
Simonet, G.: Two FOL Semantics for Simple and Nested Conceptual Graphs. In: Mugnier, M.-L., Chein, M. (eds.) ICCS 1998. LNCS (LNAI), vol. 1453, p. 240. Springer, Heidelberg (1998)
Salvat, E., Mugnier, M.L.: Sound and complete forward and backward chainings of graph rules. In: Eklund, P., Mann, G.A., Ellis, G. (eds.) ICCS 1996. LNCS (LNAI), vol. 1115, pp. 248–262. Springer, Heidelberg (1996)
Sowa, J.F.: Conceptual Structures - Information Processing in Mind and Machine. Addison-Wesley, Reading (1984)
Sowa, J.F.: Conceptual Graphs: Draft Proposed American National Standard. In: Tepfenhart, W.M. (ed.) ICCS 1999. LNCS (LNAI), vol. 1640, pp. 1–65. Springer, Heidelberg (1999)
Wermelinger, M.: Conceptual Graphs and First-Order Logic. In: Ellis, G., Rich, W., Levinson, R., Sowa, J.F. (eds.) ICCS 1995. LNCS (LNAI), vol. 954. Springer, Heidelberg (1995)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2000 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mugnier, ML. (2000). Knowledge Representation and Reasonings Based on Graph Homomorphism. In: Ganter, B., Mineau, G.W. (eds) Conceptual Structures: Logical, Linguistic, and Computational Issues. ICCS 2000. Lecture Notes in Computer Science(), vol 1867. Springer, Berlin, Heidelberg. https://doi.org/10.1007/10722280_12
Download citation
DOI: https://doi.org/10.1007/10722280_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-67859-5
Online ISBN: 978-3-540-44663-7
eBook Packages: Springer Book Archive