 A graphical representation for logic.
 Full firstorder logic plus metalanguage capabilities.
 Same modeltheoretic semantics as the Knowledge Interchange
Format (KIF).
 Same expressive power: Anything represented in CGs or KIF
can be translated to a logically equivalent form in the other.

Example: A cat is on a mat.


Boxes are called concepts, and circles are called
conceptual relations. The default quantifier for each concept
is the existential, which says that something of the specified type
exists.
Each conceptual relation has one or more arcs. In KIF and CGIF
the arcs are represented sequentially by a list of variables (KIF) or
coreference labels (CGIF), prefixed with a question mark.
In KIF, the quantifier ("exists" or "forall") and its associated
"sort", such as Cat or Mat, corresponds to a declaration in
a programming langage. In CGIF, an asterisk in front of a coreference
label declares the concept in which the quantifier and type
are associated with the correference label.
In the display form, the arcs
are numbered from 1 to some upper limit n, which depends
on the relation type. Alternatively, the first arc may be shown
as an arrow pointing toward the circle, and the nth arc
may be shown as an arrow pointing away from the circle.

Example: Every cat is on a mat.


The universal quantifier is indicated by a symbol, such as
an upsidedown A in the display form or by @every in CGIF.
By default, universal quantifiers have precedence over the existential
quantifiers. If necessary, special concept boxes called contexts
may be used to delimit the scope of quantifiers.

Example: A person is between a rock and a hard place.


The first two arcs of the Betw relation are numbered to distinguish
them, and the last (third) arc is distinguished by the arrow pointing
away from the circle. The arrow on the third arc may be replaced
by the number 3.

Example: John is going to Boston by bus.


In logic, many different conventions are used for representing
the concepts expressed by verbs. For some purposes, the simplest choice
is to represent a verb by a relation with one arc or argument for each
participant. Unfortunately, this solution cannot be easily generalized
to handle all the options that may occur.
For example, the sentence John is going would require a monadic
relation, John is going to Boston would require a dyadic relation,
and John is going to Boston by bus at noon would require
a tetradic relation.

Example: John is going to Boston by bus.


 CG display form:
 CGIF:
[Go: *x] [Person: 'John' *y] [City: 'Boston' *z] [Bus: *w]
(Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?w)
 KIF:
(exists ((?x Go) (?y Person) (?z City) (?w Bus))
(and (Name ?y John) (Name ?z Boston)
(Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?w)))
This representation treats verbs and nouns on an equal footing:
the verb go is represented by a concept type Go, which is
treated in the same way as the concept types for representing nouns.
The relations named Agnt, Dest, and Inst represent the
thematic roles of
agent, destination, and instrument, which are commonly used
in linguistics. With such relations, arbitrarily many participants
and qualifiers can be linked to the same concept.

Defining Relations by Lambda Expressions


A definition is a metalevel statement that associates a name with
a definition of the entity it names. In this example, the Def
relation associates the relation name GoR3 with a triadic
lambda expression, which defines the corresponding relation.
The concept of type LambdaExpression contains a nested conceptual
graph, in which the Greek letter lambda is used to mark three
of the concepts as formal parameters. The rule of
lambda expansion allows any graph that contains a relation
of type GoR3 to be expanded to a graph with a concept of type Go
linked to relations of types Agnt, Dest, and Inst. The inverse rule of
lambda contraction allows any graph with a concept of type Go
linked to three relations of type Agnt, Dest, and Inst to be contracted
to a graph with a relation of type GoR3. Equivalent definition
techniques and rules for expansion and contraction are available
in CGIF and KIF.

Example: Tom believes Mary wants to marry a sailor.


 CG display form:
 CGIF:
[Person: *x1 'Tom'] [Believe *x2] (Expr ?x2 ?x1)
(Thme ?x2 [Proposition:
[Person: *x3 'Mary'] [Want *x4] (Expr ?x4 ?x3)
(Thme ?x4 [Situation:
[Marry *x5] (Agnt ?x5 ?x3) (Thme ?x5 [Sailor]) ]) ])
 KIF:
(exists ((?x1 person) (?x2 believe))
(and (name ?x1 'Tom) (expr ?x2 ?x1)
(thme ?x2
(exists ((?x3 person) (?x4 want) (?x8 situation))
(and (name ?x3 'Mary) (expr ?x4 ?x3) (thme ?x4 ?x8)
(dscr ?x8 (exists ((?x5 marry) (?x6 sailor))
(and (Agnt ?x5 ?x3) (Thme ?x5 ?x6)))))))))
In this example, the concepts of type Proposition and Situation
represent contexts that contain nested conceptual graphs.
The context boxes delimit the scope of quantifiers and other logical
operators. The sailor, whose existential quantifier occurs inside
the context of Mary's desire, which itself is nested inside the context
of Tom's belief, might not exist in reality.
The dotted line from the concept [Person: Mary] to the concept [T], which is
called a coreference link, shows that the inner concept [T]
has the same referent as concept to which it is linked. In CGIF, the
coreference link corresponds to a pair of coreference labels that
associate the defining node [Person: Mary *x] with a
bound node [T: ?x]. The type T, which represents the most
general type at the top if the type hierarchy, is true of everything;
therefore, a node such as [T: ?x] can be simplified to [?x] or
just ?x in the CGIF notation.

Example: There is a sailor that Tom believes Mary
wants to marry.


 CG display form:
 CGIF:
[Person: *x1 'Tom'] [Sailor: *x6] [Believe *x2] (Expr ?x2 ?x1)
(Thme ?x2 [Proposition:
[Person: *x3 'Mary'] [Want *x4] (Expr ?x4 ?x3)
(Thme ?x4 [Situation:
[Marry *x5] (Agnt ?x5 ?x3) (Thme ?x5 ?x6) ]) ])
 KIF:
(exists ((?x1 person) (?x6 sailor) (?x2 believe))
(and (name ?x1 'Tom) (expr ?x2 ?x1)
(thme ?x2
(exists ((?x3 person) (?x4 want) (?x8 situation))
(and (name ?x3 'Mary) (expr ?x4 ?x3) (thme ?x4 ?x8)
(dscr ?x8 (exists ((?x5 marry)
(and (agnt ?x5 ?x3) (thme ?x5 ?x6)))))))))
In this example, the sailor is mentioned outside of any nested clauses.
In the corresponding logic, the concept [Sailor] or the existential
quantifier for ?x6 has also been moved outside the nested contexts.
Therefore, a particular sailor is presumed to exist in the actual world.
Another possibility, represented by the sentence Tom believes there
is a sailor that Mary wants to marry, could be represented
by moving the concept [Sailor] or the corresponding quantifier
into the middle context, which represents Tom's belief.

Why Graphs?


 Readability: Graphs reduce the number of variables by
showing connections directly.
 Different algorithms:
Some algorithms are more efficient on graphs.
Some algorithms are more efficient on linear forms.
Ability to mix and match tools that take advantage of different
structural properties.
 More natural for certain applications:
Map cities to nodes and highways to arcs.
Show flow through programs, electrical wiring, and plumbing.
Direct mapping to computer networks.

International User Community


 International Conferences on Conceptual Structures (ICCS)
 Held annually since 1993 in Canada, United States, Australia,
France, and Germany.
 ICCS 2001 at Stanford from July 30 to August 3:
http://www.ksl.stanford.edu/iccs2001/
 ICCS 2002 will be held in Bulgaria.

Bibliography



Chein, Michel, ed. (1996) Revue d'Intelligence artificielle,
Special Issue on Conceptual Graphs, vol. 10, no. 1.

Eklund, Peter W., Gerard Ellis, & Graham Mann, eds. (1996)
Conceptual Structures: Knowledge Representation as
Interlingua, Lecture Notes in AI 1115, SpringerVerlag, Berlin.

Ellis, Gerard, Robert A. Levinson, William Rich,
& John F. Sowa, eds. (1995) Conceptual Structures:
Applications, Implementation, and Theory,
Lecture Notes in AI 954, SpringerVerlag, Berlin.

Ganter, Bernhard, & Guy W. Mineau, eds. (2000) Conceptual Structures:
Logical, Linguistic, and Computational Issues,
Lecture Notes in AI 1867, SpringerVerlag, Berlin.

Hansen, Hans Robert, Robert Mühlbacher, & Gustaf Neumann (1992)
Begriffsbasierte Integration von Systemanalysemethoden,
PhysicaVerlag, Heidelberg. Distributed by SpringerVerlag.

Lukose, Dickson, Harry Delugach, Mary Keeler, Leroy Searle,
& John Sowa, eds. (1997) Conceptual Structures:
Fulfilling Peirce's Dream,
Lecture Notes in AI 1257, SpringerVerlag, Berlin.

Nagle, T. E., J. A. Nagle, L. L. Gerholz, & P. W. Eklund, eds. (1992)
Conceptual Structures: Current Research and Practice,
Ellis Horwood, New York.

Nogier, JeanFrançois (1991) Génération
automatique de langage et graphes conceptuels, Hermès, Paris.

Mineau, Guy W., Bernard Moulin, & John F. Sowa, eds. (1993)
Conceptual Graphs for Knowledge Representation,
Lecture Notes in AI 699, SpringerVerlag, Berlin.

Mugnier, MarieLaure, & Michel Chein, eds. (1998) Conceptual
Structures: Theory, Tools, and Applications,
Lecture Notes in AI 1453, SpringerVerlag, Berlin.

Pfeiffer, Heather D., & Timothy E. Nagle, eds. (1993)
Conceptual Structures: Theory and Implementation,
Lecture Notes in AI 754, SpringerVerlag, Berlin.

Rassinoux, AnneMarie (1994) Extraction et Représentation
de la Connaissance tirée de Textes Médicaux,
Éditions Systèmes et Information, Geneva.

Schröder, Martin (1994) Erwartungsgestützte Analyse
medizinischer Befundungstexte: Ein wissensbasiertes Modell zur
Sprachverarbeitung, InfixVerlag, Sankt Augustin.

Sowa, John F. (1976) "Conceptual graphs for a database interface,"
IBM Journal of Research and Development, vol. 20, no. 4,
pp. 336357.

Sowa, John F. (1984) Conceptual Structures: Information Processing
in Mind and Machine, AddisonWesley, Reading, MA.

Sowa, John F., ed. (1992) KnowledgeBased Systems,
Special Issue on Conceptual Graphs, vol. 5, no. 3, September 1992.

Sowa, John F. (2000)
Knowledge Representation: Logical,
Philosophical, and Computational Foundations,
Brooks Cole Publishing Co., Pacific Grove, CA.

Stumme, Gerd, ed. (2000) Working with Conceptual Structures:
Contributions to ICCS'2000, ShakerVerlag, Aachen.

Tepfenhart, William, and Walling Cyre, eds. (1999)
Conceptual Structures: Standards and Practices,
Lecture Notes in AI 1640, SpringerVerlag, Berlin.

Tepfenhart, William M., Judith P. Dick, and John F. Sowa, eds. (1994)
Conceptual Structures: Current Practice,
Lecture Notes in AI 835, SpringerVerlag, Berlin.

Way, Eileen C. (1991) Knowledge Representation and Metaphor,
Kluwer Academic Publishers, Dordrecht.

Way, Eileen C., ed. (1992) Journal of Experimental and
Theoretical Artificial Intelligence (JETAI),
Special Issue on Conceptual Graphs, vol. 4, no. 2.
This is a revised version of a presentation by John F. Sowa
at the meeting of ISO SC32 WG2 on 3 April 2001.
Last Modified: