Editing Conceptual graph (section)

== Research branches ==

Since 1984, the model has been developed along three main directions: a graphical interface for [[first-order logic]], a [[Diagram|diagrammatic]] calculus of logics, and a [[graph (discrete mathematics)|graph]]-based [[knowledge representation and reasoning]] model.{{sfn|Sowa|1984}}

=== Graphical interface for first-order logic ===
[[File:Cat-on-mat.svg|thumb|left|250px|Elsie the cat is sitting on a mat]]
In this approach, a formula in [[first-order logic]] (predicate calculus) is represented by a labeled graph.

A linear notation, called the Conceptual Graph Interchange Format (CGIF), has been standardized in the [[ISO standard]] for [[common logic]].

The diagram above is an example of the ''display form'' for a conceptual graph. Each box is called a ''concept node'', and each oval is called a ''relation node''. In CGIF, this CG would be represented by the following statement:

{{code|[Cat Elsie] [Sitting *x] [Mat *y] (agent ?x Elsie) (location ?x ?y)}}

In CGIF, brackets enclose the information inside the concept nodes, and parentheses enclose the information inside the relation nodes. The letters x and y, which are called ''coreference labels'', show how the concept and relation nodes are connected. In CLIF, those letters are mapped to variables, as in the following statement:

{{code|(exists ((x Sitting) (y Mat)) (and (Cat Elsie) (agent x Elsie) (location x y)))}}

As this example shows, the asterisks on the coreference labels {{code|*x}} and {{code|*y}} in CGIF map to existentially quantified variables in CLIF, and the question marks on {{code|?x}} and {{code|?y}} map to bound variables in CLIF. A universal quantifier, represented {{code|@every*z}} in CGIF, would be represented {{code|forall (z)}} in CLIF.

Reasoning can be done by translating graphs into logical formulas, then applying a logical [[inference engine]].

=== Diagrammatic calculus of logics ===
Another research branch continues the work on [[existential graph]]s of [[Charles Sanders Peirce]], which were one of the origins of conceptual graphs as proposed by Sowa. In this approach, developed in particular by Dau {{harv|Dau|2003}}, conceptual graphs are conceptual [[diagram]]s rather than graphs in the sense of [[graph theory]], and reasoning operations are performed by operations on these diagrams.

=== Graph-based knowledge representation and reasoning model ===
Key features of GBKR, the graph-based knowledge representation and reasoning model developed by Chein and Mugnier and the Montpellier group, can be summarized as follows:{{sfn|Chein|Mugnier|2009}}

* All kinds of knowledge (ontology, rules, constraints and facts) are labeled graphs, which provide an intuitive and easily understandable means to represent knowledge.
* Reasoning mechanisms are based on graph notions, basically the classical notion of [[graph homomorphism]]; this allows, in particular, to link basic reasoning problems to other fundamental problems in computer science (e.g., problems concerning [[Conjunctive query|conjunctive queries]] in [[relational database]]s, or [[constraint satisfaction problem|constraint satisfaction problems]]).
* The formalism is logically founded, i.e., it has a semantics in [[first-order logic]] and the inference mechanisms are sound and complete with respect to deduction in first-order logic.
* From a computational viewpoint, the graph homomorphism notion was recognized in the 1990s as a central notion, and complexity results and efficient algorithms have been obtained in several domains.

COGITANT and COGUI are tools that implement the GBKR model. COGITANT is a library of [[C++]] classes that implement most of the GBKR notions and reasoning mechanisms. COGUI is a graphical user interface dedicated to the construction of a GBKR knowledge base (it integrates COGITANT and, among numerous functionalities, it contains a translator from GBKR to [[RDF Schema|RDF/S]] and conversely).