W3C home > Mailing lists > Public > www-rdf-interest@w3.org > March 2004

CGs for the Semantic Web: a short bibliography

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

This archive was generated by hypermail 2.3.1 : Tuesday, 18 February 2014 13:20:06 UTC