- From: Jean-François Baget <j.f.baget@wanadoo.fr>
- Date: Tue, 2 Mar 2004 16:28:24 +0100
- To: <www-rdf-interest@w3.org>
- Message-ID: <000001c4006b$05f1f460$5600020a@inrialpes.fr>
Hi, As asked during the W3C Tech Plenary meeting (Semantic Web Interest Group), here is a short Conceptual Graphs bibliography (I admit it is a very “Montpellier school of CGs”-oriented one), including some papers that can be interesting for RDF and its extensions (mainly rules and contexts). I focus here on technical results: syntax, semantics, inference operators. A) Simple Conceptual Graphs (correspond to RDF, positive conjunctive existential first-order logics, positive datalog, …) [1] John F. Sowa “Conceptual Graphs for a Database Interface” IBM Journal of Research and Development 20(4), pages 6-57, 1976 Comment: Foundation paper, CGs as a uniform interface for both database tables and positive queries. Inferences with graph-based elementary operations. [2] John F. Sowa “Conceptual Structures: Information Processing in Mind and Machine” Addison-Wesley, 1984 Comment: The book that popularized CGs. Contains [1] (but now refers directly to logics instead of databases) as well as many ideas to extend the basic model. [3] Michel Chein & Marie-Laure Mugnier “Conceptual Graphs: fundamental notions” Revue d’Intelligence Artificielle 6(4), pages 365-406, 1992 Comment : Reformulate Sowa’s elementary reasoning operations as a global operation (projection), which is a kind of graph homomorphism. The necessary result for efficient deduction algorithms. Also introduces irredundant graphs (the smallest element of a the class of equivalent CGs). The irredundant is called core by graph theoricians (see Hell & Nesetril, 1979). [4] Bikash C. Gosh & Vilas Wuwongse “A Direct Proof Procedure for Definite Conceptual Graphs Programs” Proceedings of ICCS’95 LNCS 954, Springer, pages 158-172, 1995 Comment: Neither Sowa’s elementary operations nor Chein & Mugnier projection is complete w.r.t. CGs logical semantics! A solution is to put the query into its anti-normal form. Problem: I find it difficult to write efficient algorithms with the query in this form… [5] Michel Chein & Marie-Laure Mugnier « Conceptual Graphs are also Graphs » Actes des 4° journées du laboratoire d’informatique de Paris-Nord Available as a research report RR-LIRMM 95-003, 1995 Comment: Independently discover the same problem as [4]. Their solution is to put the facts graph into normal form. Good News: RDF graphs are in normal form, so we won’t have to transform the web. [6] Marie-Laure Mugnier « Knowledge Representation and Reasonings Based on Graph Homomorphism » Proceedings of ICCS’2000 LNCS 1867, Springer, pages 172-192, 2000 Comment: A “Montpellier school of CGs survey”. You can begin your reading with this one. Also contains a CG Projection-CSP (Constraint Satisfaction Problem) equivalence, useful for algorithmic optimization. [7] Jean-François Baget “Conceptual Graphs Revisited: Hypergraphs and Conjunctive Types for Efficient Projection Algorithms” Proceedings of ICCS’2003 LNAI 2746, Springer, pages 229-242, 2003 Comment: Capitalizing on the CG-CSP equivalence of [6], an example on how to use efficient CSP optimization techniques for CG projection. Also contains a model-theoretic semantics for CGs (usually given via logical translation). B) Simple Conceptual Graphs and RDF (or using CG Projection for CSP entailment, see optimization in [7]) [8] Olivier Corby & Rose Dieng & Cédric Hébert “A Conceptual Graph Model for W3C Resource Description Framework” Proceedings of ICCS’2000 LNCS 1867, Springer, pages 468-482, 2000 Comment: A transformation of RDF to CGs such that CG projection is equivalent to RDF entailment. [9] Sir Tim Berners-Lee “Conceptual Graphs and the Semantic Web” http://www.w3.org/DesignIssues/CG.html, 2001 Comment: Hey, there’s an old language that looks a lot like RDF! [9] Jean-François Baget « Homomorphismes d’hypergraphes pour la projection en RDF/RDFS » RSTI - L’Objet 10, LMO’2004, pages 203-216, 2004 Comment : Another transformation RDF->CG, this time it is an exact translation of RDF semantics. The goal is to be resistant to further extensions of the model. CG extensions can now be directly tranlated into RDF (e.g. rules and nested graphs). Sorry only in french for the time being… C) CG Rules (of form “IF graph1 THEN graph2”, logically translated into Tuple Generating Dependencies) FORALL X1 … Xk (CONJUNCTION(X1,…,Xk) --> (EXISTS Y1, …, Yp (CONJUNCTION(X1,…,Xk,Y1,…,Yp))) Where CONJUNCTION(...) is a conjunction of atomic formulas whose variables are restricted to those appearing in its arguments. [2] Comment: Rules as a simple and intuitive interface for logical nested double negation. [10] Jean Fargues & Marie-Claude Landau & Anne Dugourd & Laurent Catach « Conceptual Graphs for Semantics and Knowledge Processing » IBM Journal of Research and Development 30(1), pages 70-79, 1986 Comment: Prolog-like use of CG rules. [11] Anand S. Rao & Norman Y. Foo “CONGRES: Conceptual Graphs Reasoning System” Proc. Of the 3rd Conference on Artificial Intelligence Applications IEEE Computer Society Press, pages 87-92, 1987 Comment: Another version of rules. [4] Comment: Yet another version of rules. [12] Eric Salvat & Marie-Laure Mugnier « Sound and Complete Forward and Backward Chainings of Graphs Rules” Proc of ICCS’96 LNCS 1115, Springer, pages 248-262, 1996. Comment: Both algorithms rely on projection. Interesting optimization for backward chaining: unifies subgraphs instead of atoms. [13] Eric Salvat “Theorem Proving Using Graph Operations in the Conceptual Graph Formalism” Proc. of ECAI’98 John Wiley and sons, pages 356-360, 1998 Comment: refinement of [12] [14] Stephane Coulondre & Eric Salvat “Piece Resolution: Towards Larger Perspectives” Proc of ICCS’98 LNCS 1453, pages 179-193, 1998. Comment : Experimental comparison of Prolog and CG backward chaining of [12,13]. Also proof of undecidability of the deduction problem. [15] Jean-François Baget “Improving the Forward Chaining Algorithm for Conceptual Graphs Rules” Proc. of KR’2004 To appear. Comment: Forward chaining is often inefficient, but sometimes unavoidable (e.g. mixing rules and global constraints). Propose the compilation of a set of rules, leading to a more efficient algorithm and new decidability results. [16] Juliette Dibie & Ollivier Haemmerle & Stephane Loiseau “A Semantic Validation of Conceptual Graphs” Proc of ICCS’98 LNCS 1453, pages 80-93, 1998. Comment : Constraints have the same representation as rules, but a different meaning (each time we deduce information A, we must also find information B or the graph is inconsistant). They are thus used for semantic validation ad not for deduction. [17] Jean-François Baget & Marie-Laure Mugnier “Extensions of Simple Conceptual Graphs: the Complexity of Rules and Constraints” Journal of Artificial Intelligence Research, 16, pages 425-465, 2002. http://www.cs.washington.edu/research/jair/contents/v16.html Comment: combines constraints of [16], inference rules of [12] and evolution rules to obtain various languages. Compatible with optimizations in [15]. D) Nested CGs (can be used for contexts) [2] Comment: as usual, he had the idea. Technical details follow. [18] Marie-Laure Mugnier & Michel Chein « Représenter des connaissances et raisonner avec des graphes » Revue d’Intelligence Artificielle 10(1), pages 7-56, 1996 Comment : Formalization of Nested CGs and definition of the inference operator. [19] Genevieve Simonet “Two FOL Semantics for Simple and Nested Conceptual Graphs” Proc. of ICCS’98 LNCS 1453, pages 240-254, 1998. Comment : Gives a logical translation compatible with the inference operator in [18], and a more expressive semantics, but where the normality condition can be trickier than in [4,5]. [20] Anne Preller & Marie-Laure Mugnier & Michel Chein « Logic for Nested Graphs » Computational Intelligence, 14(3), pages 335-357, 1998. Comment: Yet another semantics for Nested CGs, this time they are translated into nice coloured formulas. [21] Michel Chein & Marie-Laure Mugnier & Genevieve Simonet “Nested Graphs : A Graph-Based Knowledge Representation Model with FOL Semantics” Proc. of KR’98 Morgan Kaufman, pages 524-435, 1998. Comment: clarifies [19] [22] Jean-François Baget “Extending the CG Model by Simulations” Proc. of ICCS’2000 LNCS 1867, Springer, pages 277-291, 2000. Comment: Transforms Nested CGs into Simple CGs, while preserving all inferences. Interest: Nested RDF graphs can have their syntax written in standard RDF. E) Shameless self-promotion (my thesis covers almost all these subjects – without RDF--, has a larger bibliography, but it is in french…) [23] Jean-François Baget « Représenter des connaissances et raisonner avec des hypergraphes: de la projection à la dérivation sous contraintes » PhD Thesis, Université de Montpellier II, 2001. http://www.lirmm.fr/~baget/These Jean-François Baget INRIA Rhône-Alpes jean-francois.baget@inrialpes.fr Tel: 04 76 61 53 27
Received on Tuesday, 2 March 2004 10:37:29 UTC