Conceptual Graphs

 
 
 

Warning This document is not an ISO International Standard. It is distributed for review and comment. It is subject to change without notice and may not be referred to as an International Standard.  Recipients of this document are invited to submit, with their comments, notification of any relevant patent rights of which they are aware and to provide supporting documentation.

 
 
 

Document type:  International standard

Document stage:  (20) Preparation

Document language: E

Comments and suggestions should be sent to the editor, John F. Sowa.
 
 
 
 

Table of Contents

1 Scope

2 Conformance

3 Normative References

4 Terms and Definitions

5 CG Representations

Foreword

International Standards are drafted in accordance with the rules given in the ISO/IEC Directives, Part 3.

Draft International Standards adopted by the technical committees are circulated to the member bodies for voting. Publication as an International Standard requires a pproval by at least 75% of the member bodies casting a vote.

International Standard ISO nnn-n was prepared by Technical Committee ISO/JTC 1, Information Technology Standards, Subcommittee SC 32, Data Management and Interchange. 

1 Scope

The CGIF and KIF notations have the same model-theoretic semantics, which is specified in ISO mmm-m. For any CGIF statement s, the denotation of s is defined as the denotation of the corresponding KIF statement generated by the translation rules of Chapter 9 of ISO nnn-n, which is then evaluated according to the model theory specified in ISO mmm-m.

ISO nnn-n also provides guidance for implementers of IT systems that use conceptual graphs as an internal representation or as an external representation for interchange with other IT systems. The external representations are readable by humans and may also be used in communications between humans or between humans and machines.

2 Conformance

1. The style specifies how much nonsemantic information is preserved by the IT system that accepts and generates information represented in CGIF.
2. The expressiveness specifies the largest subset of semantic features defined by the abstract syntax of Chapter 6 that can be represented in CGIF that is accepted and generated by the IT system.

3 Normative References

ISO/IEC 10646, Information Technology (IT) - Universal Multiple-Octet Coded Character Set (UCS).

4 Terms and Definitions

abstract syntax (AS).

A notation-independent specification of all semantically significant features of conceptual graphs.

actor.

A conceptual relation that is used to represent functional dependencies. Its semantics may be computed or otherwise determined by an IT system external to the current module.

arc.

An ordered pair <r,c>, which is said to link a conceptual relation r to a concept c.

blank graph.

An empty CG containing no concepts or conceptual relations.

bound label.

An identifier prefixed with the character "?" that marks a bound concept of a coreference set.

catalog of individuals.

A context of type CatalogOfIndividuals whose designator is a CG that contains a unique concept for each individual marker that appears in a module. It may also contain additional concepts and relations that describe the individuals and the relationships among them.

compound graph.

A conceptual graph that is not simple. It contains one or more contexts or defined quantifiers.

concept.

A node in a CG that refers to an entity, a set of entities, or a range of entities.

conceptual graph (CG or graph).

An abstract representation for logic with nodes called concepts and conceptual relations, linked together by arcs.

conceptual graph interchange form (CGIF).

A normative concrete representation for conceptual graphs.

conceptual relation (relation).

A node in a CG that has zero or more arcs, each of which links the conceptual relation to some concept.

conformance pair.

A pair of identifiers, called the style and expressiveness, which specify the subset of CGIF that may be accepted or generated by an IT system.

conformity operator.

A symbol "::" that relates types to individual markers. If t::i is true, the entity identified by the individual marker i is said to conform to the type t.

context.

A concept that contains a nonblank CG that is used to describe the referent of the concept.

coreference label.

A defining label or a bound label used to identify the concepts that belong to a particular coreference set.

coreference link.

A dotted line that links concepts that belong to the same coreference set. Coreference links are used only in the nonnormative DF and LF; in CGIF, they are replaced by coreference labels.

coreference set.

A set of concepts in a CG that refer to the same entity or entities. In CGIF and LF, the members of a coreference set are marked with coreference labels that have matching identifiers; in DF, they may be linked by dotted lines called coreference links.

defined quantifier.

Any quantifier other than the existential. Defined quantifiers are defined in terms of conceptual graphs that contain only existential quantifiers.

defining label.

An identifier prefixed with the character "*" that marks the defining concept of a coreference set.

designator.

A symbol in the referent field of a concept that determines the referent of the concept by showing its literal form, specifying its location, or describing it by a nested CG.

display form (DF).

A nonnormative concrete representation for conceptual graphs that uses graphical displays for better human readability than CGIF.

encoded literal.

An encoded representation of a literal other than a number or a character string. It may be used to specify strings in a language other than conceptual graphs or MIME encodings of text, images, sound, and video.

entity.

Anything that exists, has existed, or may exist.

extended syntax (ES).

Extensions to the CGIF syntax defined in terms of the basic features of CGIF.

first-order logic (FOL).

A version of logic that forms the foundation of many IT languages and systems, including SQL. See Chapter 9 for further information.

formal parameter (parameter).

A concept in a lambda expression whose referent is not defined until the concept is linked to some coreference set whose referent is defined.

functional relation.

A conceptual relation type t that contains one or more functional dependencies. If t has valence n&ge;2, it may be declared to be functional in its last m arcs for some m<n. The first n-m arcs are called input arcs, and the last m arcs are called output arcs. Each output arc must be functionally dependent on all of the input arcs: formally, if r is any conceptual relation of type t, the referent of each concept attached an output arc of r is uniquely determined when all the referents of the concepts attached to its input arcs are specified. If a functional relation is represented by an actor node, each input arc of the relation is represented by an input arc of the actor, and each output arc of the relation is represented by an output arc of the actor.

higher-order logic (HOL).

An extension to first-order logic that is represented by conceptual graphs and KIF. See Chapter 9 for further information.

identifier.

A character string beginning with a letter or the underscore character "_" and continuing with zero or more letters, digits, or underscores. Case is significant: two identifiers that differ only in the case of one or more letters are considered distinct.

indexical.

A designator represented by the character "#" followed by an optional identifier. It represents a context-dependent reference that is resolved by replacing the indexical with a coreference label.

individual marker.

A designator, represented by the character "#" followed by an integer, used as an index of some entry in the catalog of individuals of the current module. Individual markers cannot be used to identify individuals across different modules, but within any single module, they can serve as unique identifiers or surrogates for the entities referenced in that module.

module (KB).

A context with three nested contexts: a type hierarchy, a catalog of individuals, and an outermost context of type Assertion.

Knowledge Interchange Format (KIF).

A language for representing logic that has a model-theoretic semantics equivalent to the semantics of conceptual graphs.

lambda expression.

A CG with zero or more concepts marked as formal parameters. There is no semantic distinction between a CG with no formal parameters and a zero-adic lambda expression.

layout information.

Specification of the shapes and positions of the nodes and arcs of a CG when it is displayed on a two-dimensional surface. The layout information is not represented in the abstract syntax, and it has no effect on the CG semantics.

linear form (LF).

A nonnormative concrete representation for conceptual graphs intended for better human readability than CGIF, but without requiring graphical displays.

negation.

A context of type Proposition to which is attached a monadic conceptual relation of type Neg or its abbreviation by the character "~" or "¬".

nested conceptual graph.

A CG that is used as a designator in the referent field of some concept.

outermost context.

A context of type Assertion containing a nested CG that asserts the facts and axioms of some module.

quantifier.

A symbol in the referent field of a concept that determines the range of entities in the referent of the concept. The default quantifier is the existential, which is represented by a blank; all others are defined quantifiers.

referent.

The entity or entities that a concept refers to.

referent field.

The area in a concept where the referent is specified.

signature.

For any conceptual relation r with valence n, a list of n types that restrict the types of concepts that may be linked to each of the n arcs of r.

simple graph.

A conceptual graph that contains no contexts, negations, or defined quantifiers.

singleton graph.

A CG that contains a single concept and no conceptual relations.

special context.

A kind of context defined by the extended syntax in Section 8.1. Special contexts include negations and contexts whose type label is one of the following: If, Then, Else, Elif, Either, Or, And, Equivalent, Iff.

star graph.

A CG that contains a single conceptual relation and the concepts that are attached to each of its arcs.

type field.

The area in a concept node where the concept type is specified.

type hierarchy.

A context of type TypeHierarchy that specifies a partial ordering of type labels, some or all of which are defined by monadic lambda expressions.

type label.

An identifier that specifies a type of concept, conceptual relation, or actor.

valence.

A nonnegative integer that specifies the number of arcs that link a conceptual relation to concepts. All conceptual relations with the same type label have the same valence. A conceptual relation or relation label of valence n is said to be n-adic; monadic is synonymous with 1-adic, dyadic with 2-adic, and triadic with 3-adic.

5 CG Representations

5.1 Abstract and Concrete Syntax

For transmitting conceptual graphs between IT Systems that conform to ISO nnn-n, Chapter 7 specifies the concrete syntax of the conceptual graph interchange form (CGIF) and its mapping to the abstract syntax of Chapter 6. Chapter 8 specifies syntactic extensions to CGIF and their translation to the basic CGIF of Chapter 7. For communication with human users, two other concrete notations have are commonly used in conforming IT systems: a graphic notation called the display form (DF) and a more compact notation called the linear form (LF). Although the CGIF notation and the extensions are specified in the normative Chapters 7 and 8, the DF and LF notations are described only by recommended guidelines in the nonnormative Annex A. Chapter 9 defines the semantics of conceptual graphs by a normative translation to predicate calculus.

5.2 Example

Figure 1. CG Display Form for "John is going to Boston by bus."

In DF, concepts are represented by rectangles: [Go], [Person: John], [City: Boston], and [Bus]. Conceptual relations are represented by circles or ovals: (Agnt) relates [Go] to the agent John, (Dest) relates [Go] to the destination Boston, and (Inst) relates [Go] to the instrument bus. For n-adic relations, the arcs are numbered from 1 to n; for dyadic relations, the number 1 may be replaced by an arrowhead pointing toward the relation, and the number 2 may be replaced by an arrowhead pointing away from the relation.

As a mnemonic aid, an arrow pointing toward the circle may be read "has a(n)"; an arrow pointing away may be read "which is a(n)"; and any abbreviations may be expanded to the full forms. With this convention, Figure 1 could be read as three English sentences:

• Go has an agent which is a person John.
• Go has a destination which is a city Boston.
• Go has an instrument which is a bus.

The linear form for CGs is intended as a more compact notation than DF, but with good human readability. It is exactly equivalent in expressive power to the abstract syntax and the display form. Following is the LF for Figure 1:

[Go]-
   (Agnt)->[Person: John]
   (Dest)->[City: Boston]
   (Inst)->[Bus].

Both DF and LF are designed for communication with humans or between humans and machines. For communication between machines, the conceptual graph interchange form (CGIF) has a simpler syntax and a more restricted character set. Following is the CGIF for Figure 1:

[Go *x] (Agnt ?x [Person: John]) (Dest ?x [City: Boston]) (Inst ?x [Bus])

(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)))

6 Abstract Syntax

6.1 Conceptual Graph

• Every arc a of g is a pair (r,c) consisting of a conceptual relation r and a concept c in g. The arc a is said to belong to r; it is said link r to c; but it does not belong to c.
• A conceptual graph g may have concepts that are not linked to any conceptual relation; but every arc that belongs to any conceptual relation r in g must link r to exactly one concept c in g.
• Three kinds of conceptual graphs have distinguished names:
1. The blank is an empty conceptual graph with no concepts, conceptual relations, or arcs.
2. A singleton is a conceptual graph that consists of a single concept, but no conceptual relations or arcs.
3. A star is a conceptual graph that consists of a single conceptual relation r, every arc that belongs to r, and every concept c that is linked by some arc (r,c) that belongs to r.

 To illustrate this definition, consider the conceptual graph in Figure 1 for the sentence John is going to Boston by bus. That CG contains four concepts, [Go], [Person: John], [City: Boston], and [Bus]; it contains three conceptual relations, (Agnt), (Dest), and (Inst); and it contains six arcs that link conceptual relations to concepts. There are no arcs that link concepts to concepts or relations to relations. Two of the arcs in the CG belong to (Agnt), two belong to (Dest), and two belong to (Inst).

Any conceptual graph g with n conceptual relations can be constructed from n star graphs, one for each conceptual relation in g. Since Figure 1 has three conceptual relations, it could be constructed from the following three star graphs, which are represented in the normative conceptual graph interchange form (CGIF):

(Agnt [Go] [Person: 'John'])
(Dest [Go] [City: 'Boston'])
(Inst [Go] [Bus])

(Agnt [Go *x] [Person: 'John'])
(Dest ?x [City: 'Boston'])
(Inst ?x [Bus])

6.2 Concept

Comment.

 This abstract definition does not say how the type and referent are represented. In computer storage, they may be represented by a pair of pointers, one pointing to a specification of the concept type and the other pointing to a specification of the referent. In the concrete notations, the type field is on the left, and the referent field is on the right. In the concept [Bus], "Bus" is the type, and the referent field contains a blank, which represents an existential quantifier; the actual referent is a physical entity of type Bus that exists somewhere in the world. In the concept [Person: John], "Person" specifies the type, and the name "John" designates some person who is the referent.

6.3 Conceptual Relation

• The number of arcs that belong to r is equal to its valence n. A conceptual relation of valence n is said to be n-adic, and its arcs are numbered from 1 to n.
• For every n-adic conceptual relation r, there is a sequence of n concept types t₁,...,t_n, called the signature of r. A 0-adic conceptual relation has no arcs, and its signature is empty.
• All conceptual relations of the same relation type t have the same valence n and the same signature s.
• The term monadic is synonymous with 1-adic, dyadic with 2-adic, and triadic with 3-adic.

Comment.

 In Figure 1, Agnt, Dest, and Inst are dyadic relation types. Examples of monadic relation types include Psbl for possibility and Past for the past tense. A 0-adic conceptual relation is logically equivalent to the proposition stated by its defining conceptual graph. Figure 2 shows the between relation (Betw) as an example of a triadic relation (valence 3), whose first two arcs are linked to two things that are on either side of a third. That graph may be read A person is between a rock and a hard place.

Figure 2. A conceptual relation of valence 3

The signature of a relation represents a constraint on the types of concepts that may be linked to its arcs. For Agnt, the signature is (Act,Animate), which indicates that the type of the concept linked to its first arc must be Act or some subtype, such as Go, and the type of the concept linked to its second arc must be Animate or some subtype, such as Person. For Betw, the signature is (Entity,Entity,Entity), which shows that all three concepts must be of type Entity, which is the most general type that imposes no constraints whatever.

For a conceptual relation with n arcs, the first n-1 arcs have arrows that point toward the circle, and the n-th or last arc points away. In LF, Figure 2 may be represented in the following form:

[Person]<-(Betw)-
            <-1-[Rock]
            <-2-[Place]->(Attr)->[Hard].

6.4 Lambda Expression

• The formal parameters of e are numbered from 1 to n.
• There is a sequence (t₁,...,t_n) called the signature of e, where each t_i is the concept type of the i-th formal parameter of e. Since a 0-adic lambda expression has no formal parameters, its signature is the empty sequence.

 This abstract definition does not specify how the formal parameters are designated. The traditional notation, which is used in LF and DF, is to mark a parameter with the Greek letter lambda &lambda;. If n is greater than 1, the parameters may be marked &lambda;₁, &lambda;₂, ..., &lambda;_n. As an example, the conceptual graph for the sentence John is going to Boston could be converted to the following dyadic lambda expression by replacing the name John with the symbol &lambda;₁ and the name Boston with &lambda;₂:

[Person: &lambda;1]<-(Agnt)<-[Go]->(Dest)->[City: &lambda;2].

To simplify the parsing, the CGIF notation avoids the character &lambda; and represents lambda expressions in a form that shows the signature explicitly:

(lambda (Person*x, City*y) [Go *z] (Agnt ?z ?x) (Dest ?z ?y))

6.5 Concept Type

• For any concept c, the type of cis either a type label in T or a monadic lambda expression.
• The type hierarchy T contains two primitive type labels Entity, called the universal type, and Absurdity, called the absurd type. The symbol "&top;" is synonymous with Entity, and the symbol "&perp;" is synonymous with Absurdity.
• For every defined type label, there is a monadic lambda expression, called its definition.
• A defined type label and its definition are interchangeable: in any position where one may occur, it may be replaced by the other.
• The partial ordering over T is determined by the subtype relation, represented by the characters "&le;" for subtype, "<" for proper subtype, "&ge;" for supertype, and ">" for proper supertype. If t is any type label, Entity&ge;t and t&ge;Absurdity; in particular, Entity>Absurdity.
• The partial ordering of type labels must be consistent with the rules of inference defined in Chapter 9.

 The type hierarchy starts with some set of primitive type labels, which includes at least Entity and Absurdity. The definitional mechanisms introduce new type labels, whose place in the hierarchy is determined by their definitions. As an example, the following equation defines the type label MaineFarmer by a lambda expression for a farmer located (Loc) in Maine:

MaineFarmer = [Farmer: λ]->(Loc)->[State: Maine].

type MaineFarmer(*x) is [Farmer: ?x]->(Loc)->[State: Maine].

[MaineFarmer: ∀]->(Attr)->[Laconic].

[ [Farmer: λ]->(Loc)->[State: Maine]: ∀]->(Attr)->[Laconic].

6.6 Relation Type

• For every relation label in R, there is a nonnegative integer n called its valence.
• For every n-adic conceptual relation r, the type of r is either a relation label in R of valence n or an n-adic lambda expression.
• For every defined relation label of valence n, there is exactly one n-adic lambda expression, called its definition.
• A defined relation label and its definition are interchangeable: in any position of a CG where one may occur, it may be replaced by the other.
• The partial ordering over R is determined by the subtype relation, with the symbols &le; for subtype, < for proper subtype, &ge; for supertype, and > for proper supertype.
• The partial ordering of relation labels must be consistent with the rules of inference defined in Chapter 9.
• If r is an n-adic relation label, s is an m-adic relation label, and n is not equal to m, then none of the following is true: r<s, r>s, r=s.

 As an example, the relation type GoingTo could be defined by a CG that makes GoingTo a synonym for a dyadic lambda expression:

[Relation: GoingTo]->(Def)->[LambdaExpression:
     [Person: &lambda;1]<-(Agnt)<-[Go]->(Dest)->[City: &lambda;2] ].

[Person: John]->(GoingTo)->[City: Boston].

[Person: John]->([Person: &lambda;1]<-(Agnt)<-[Go]-
     ->(Dest)->[City: &lambda;2])->[City: Boston].

[Person: John]<-(Agnt)<-[Go]->(Dest)->[City: Boston].

6.7 Referent

• Quantifier. A quantifier is one of two kinds: existential or defined.
• Designator. A designator is one of three kinds:
1. literal, which may be a number, a string, or an encoded literal;
2. locator, which may be an individual marker, an indexical, or a name;
3. undetermined.
• Descriptor. A descriptor is a conceptual graph, possibly blank, which is said to describe the referent.

The quantifier, designator, and descriptor determine the connections between the CG formalism and the entities it refers to. Those connections are implementation dependent because they go beyond the notation to people, things, actions, and events that are outside the computer system. An existential quantifier declares that at least one instance of the type exists; a defined quantifier may specify other quantities or amounts. A designator specifies the referent by showing its form (literal) or by pointing to it (locator); an undefined designator says nothing about the referent. The three kinds of locators differ in the way the referent is determined: an individual marker, specifies a unique concept in the catalog of individuals of a knowledge base; an indexical is a symbol that determines the referent by an implementation-defined search that is not defined by ISO nnn-n; and a name is a symbol that determines the referent by some conventions that are independent of the current module. A descriptor is a CG that describes some aspect of the referent. Following are some examples:

• A literal shows the form of a referent, as in the concept [String: "abcdefg"]. For a multimedia system, an encoded literal may represent sound, graphics, or full-motion video.
• A locator is either a name like Boston or symbol that begins with the character "#". In the concept [Tree: #23846], the locator #23846 is an individual marker that identifies some tree in a catalog of individuals. Examples of indexicals include [Person: #you] and [Book: #this]. Names include symbols like 'John Q. Public' or 'ISBN-0-534-94965-7', whose resolution to a particular referent is independent of the IT system.
• A descriptor is represented by a conceptual graph nested in the referent field of a concept, as in the following example:

[Proposition: [Cat]<-(Agnt)<-[Chase]->(Thme)->[Mouse]].

This graph may be read There exists a proposition, which states that a cat is chasing a mouse. A concept with a completely blank referent, such as [Cat], has an implicit existential quantifier and a blank conceptual graph as descriptor. Since a blank graph does not say anything about the referent, the concept [Cat] by itself simply means There exists a cat.
• An encoded literal begins with the character "%" followed by an identifier and a literal string. The identifier might be the name of a language, such as English, or it might be the name of some encoding such as GIF for images or WAV for sounds. The following concept represents a situation that is described by an English sentence:

[Situation: %English"A plumber is carrying a pipe."]

The defined quantifiers include the universal quantifier, which is represented by the character "&forall;" or the string "@every", and collections such as {1, 2, 3} or {Tom, Dick, Harry}. The translation rules specified in Section 8.2 translate the universal quantifier to an existential quantifier and a pair of negations. They translate collections to multiple concepts, each containing an existential referent.

To illustrate descriptors and literals in the referent field, Figure 3 shows a concept [Situation] with a nested conceptual graph that may be read A plumber is carrying a pipe. In the nested graph, the agent relation (Agnt) indicates that the plumber is the one who is doing the action, and the theme relation (Thme) indicates that the pipe is the theme of the action. That nested CG is a descriptor that describes the situation.

Figure 3. A conceptual graph with a descriptor and two literal referents

The situation node in Figure 3 is linked via the image relation (Imag) to a concept of type Picture, whose referent field contains an encoded literal of the image. In CGIF, the character "%" marks an encoded literal, which is followed by an identifier that specifies the format and a string that represents the encoding of an image. The situation node is also linked via an Imag relation to a concept of type Sound, whose referent field might contain an encoded literal that represents the sound. In Figure 3, the nonnormative display form uses letters to give a pronounceable approximation to the sound; a multimedia system might reproduce the sound when the user clicks on the concept node. Such features, however, are outside the scope of ISO nnn-n.

6.8 Context

• The graph g is said to be immediately nested in C, and any concept c of g is also said to be immediately nested in C.
• A concept cis said to be nested in C if either cis immediately nested in C or cis immediately nested in some context D that is nested in C.
• Two concepts cand d are said to be co-nested if either c=d or there is some context C in which cand d are immediately nested.
• If a concept x is co-nested with a context C, then any concept nested in C is said to be more deeply nested than x.
• A concept d is said to be within the scope of a concept cif either d is co-nested with cor d is more deeply nested than c.

 A context is a concept with a nested conceptual graph that describes the referent. In Figure 3, the concept of type Situation is an example of a context; the nested graph describes the situation as one in which a plumber is carrying a pipe. Figure 4 shows a CG with two contexts; it expresses the sentence Tom believes that Mary wants to marry a sailor.

Figure 4. A conceptual graph containing a nest of two contexts

In Figure 4, Tom is the experiencer (Expr) of the concept [Believe], which is linked by the theme relation (Thme) to a proposition that Tom believes. The proposition box contains another conceptual graph, which says that Mary is the experiencer of [Want], which has as theme a situation that Mary hopes will come to pass. That situation is described by another nested graph, which says that Mary (represented by the concept [&top;]) marries a sailor. The dotted line, called a coreference link, shows that the concept [&top;] in the situation box refers to the same individual as the concept [Person: Mary] in the proposition box. Following is the linear form of Figure 4:

[Person: Tom]<-(Expr)<-[Believe]->(Thme)-
   [Proposition:  [Person: Mary *x]<-(Expr)<-[Want]->(Thme)-
      [Situation:  [?x]<-(Agnt)<-[Marry]->(Thme)->[Sailor] ]].

6.9 Coreference Set

• For any coreference set C, there must be one or more concepts in C, called the dominant nodes of C, which include all concepts of C within their scope. All dominant nodes of C must be co-nested.
• If a concept cis a dominant node of a coreference set C, it may not be a member of any other coreference set.
• A concept cmay be member of more than one coreference set {C₁,C₂,...} provided that cis not a dominant node of any C_i.
• A coreference set C may consist of a single concept c, which is then the dominant node of C.

 In the display form, the members of a coreference set C may be shown by connecting them with dotted lines, called coreference links. In Figure 4, the dotted line connecting [Person: Mary] to [&top;] is an example of a coreference link. The concept [&top;] is within the scope of [Person: Mary], which is the dominant node. Since the two concepts represent the same individual, any information in the dominant node may be copied to the other node. The type label Person or the referent Mary, for example, could be copied from the dominant node to the concept [&top;].

In CGIF, which is defined in Chapter 7, the members of a coreference set are marked by coreference labels. One of the dominant nodes is marked with a defining label, prefixed with an asterisk; all the other nodes, are marked with bound labels, prefixed with a question mark.

6.10 Module

1. Type hierarchy. A context of type TypeHierarchy whose designator is a CG T that specifies a partial ordering of type labels and the monadic lambda expressions for each defined type label.
2. Relation hierarchy. A context of type RelationHierarchy whose designator is a CG R that specifies a partial ordering of relation labels, the valences of the relation labels, and the lambda expressions for each defined relation label.
3. Catalog of individuals. A context of type CatalogOfIndividuals whose designator is a CG C that contains exactly one concept for each individual marker that appears in any concept in the module. The designator may also contain other concepts and relations that describe the individuals.
4. Outermost context. A context of type Assertion whose designator is a conceptual graph O.

• The type labels in any conceptual graph or lambda expression in T, R, C, and O must be specified in T.
• The relation labels in any conceptual graph or lambda expression in T, R, C, and O must be specified in R.
• The individual markers in any conceptual graph or lambda expression in T, R, C, and O must be specified in C.

Comment.

 The outermost context of a module B corresponds to what Peirce called the sheet of assertion. Its designator is a CG that asserts the information that is assumed to be true in B. The type hierarchy and the relational hierarchy define the labels that appear in the concepts and conceptual relations of any conceptual graphs in any of the contexts nested in B. The catalog of individuals contains global information about the referents identified by individual markers in any concepts in B. As an example, the following catalog specifies individual markers for four entities: a cat, a dog, a village, and a state.

[CatalogOfIndividuals:
   [Cat: #5539]-
      (Name)->[Word: "Yojo"]
      (Attr)->[Black]
      (Loc)->[Village: #3711]->(Name)->[Word: "Croton-on-Hudson"] ]
   [Dog: #7603]-
      (Name)->[Word: "Macula"]
      (Attr)->[Spotted]
      (Loc)->[State: #2072]->(Name)->[Word: "New Hampshire"] ]]

Individuals that are not cataloged might be implied by existential quantifiers in some concepts of a module. As an example, O might assert that for every human being x, there exists exactly one father y of x and exactly one mother z of x. Any finite module, however, must eventually stop with some persons whose parents cannot be identified, even though their existence is implied.

The structures that can be represented in CGs are more general and more highly organized than the information in most commercial databases and modules. Most such systems can be represented as special cases of a CG module:

• Relational database. The names of the SQL tables map to relation labels in the relational hierarchy R, and the names of the columns in the relations map to type labels in the type hierarchy T. The rows of the tables map to star graphs stored in the outermost context O. An SQL table with n rows and m columns is translated to n star graphs, each of which contains an m-adic conceptual relation whose label is the same as the label of the table; each of the n arcs of the relation is attached to a concept whose type label is the same as the name of the corresponding column and whose referent contains the data in the table element of the corresonding row and column. Integrity constraints on the database are translated to axioms represented by CGs that are also stored in the outermost context O.
• Object-oriented database. Since O-O databases may have more structure than relational databases, their representation in a CG module may have more complex graphs. The O-O class hierarchy determines the partial ordering of the type hierarchy T, and the O-O class definitions map to lambda expressions associated with the type labels in T. The data in an O-O DB map to CGs that may be larger than the star graphs that result from a relational database.
• Expert system module. Since there are many different kinds of expert system tools, the mapping to a CG module may be defined differently for each kind of tool. Frame definitions, for example, would usually be represented in the type hierarchy while instance frames would be represented in the outermost context. For Prolog, the signatures of the predicates would be represented in the type and relation hierarchies while the rules and facts would be asserted in the outmost context.

7 Conceptual Graph Interchange Form (CGIF)

7.1 Lexical Categories

The CGIF lexical categories can be recognized by a finite-state tokenizer or preprocessor. No characters of white space (blanks or other nonprinting characters) are permitted inside any lexical item other than delimited strings (names, comments, or quoted strings). Zero or more characters of white space may be inserted or deleted between any lexical categories without causing an ambiguity or changing the syntactic structure of CGIF. The only white space that should not be deleted is inside delimited strings.

Comment.

 A comment is a delimited string with a semicolon ";" as the delimiter.

Comment  ::=  DelimitedStr(";")

DelimtedStr(D).

 A delimited string is a sequence of two or more characters that begin and end with a single character D called the delimiter. Any occurrence of D other than the first or last character must be doubled.

DelimitedStr(D)  ::=  D (AnyCharacterExcept(D) | D D)* D

Exponent.

 An exponent is the letter E in upper or lower case, an optional sign ("+" or "-"), and an unsigned integer.

Exponent ::= ("e" | "E") ("+" | "-")? UnsignedInt

Floating.

 A floating-point number is a sign ("+" or "-") followed by one of three options: (1) a decimal point ".", an unsigned integer, and an optional exponent; (2) an unsigned integer, a decimal point ".", an optional unsigned integer, and an optional exponent; or (3) an unsigned integer and an exponent.

Floating ::= ("+" | "-") ("." UnsignedInt Exponent?
                           | UnsignedInt ("." UnsignedInt? Exponent?
                                           | Exponent ) )

Identifier.

 An identifier is a string beginning with a letter or underscore "_" and continuing with zero or more letters, digits, or underscores.

Identifier  ::=  (Letter | "_") (Letter | Digit | "_")*

Identifiers beginning with "_" followed by one or more digits are generated by the Gensym rule defined in Section 8.2. Such identifiers should be avoided unless they have been generated by a call to the Gensym rule.

Integer.

 An integer is a sign ("+" or "-") followed by an unsigned integer.

Integer ::= ("+" | "-") UnsignedInt

Name.

 A name is a delimited string with a single quote "'" as the delimiter.

Name  ::=  DelimitedStr("'")

Number.

 A number is an integer or a floating-point number.

Number ::= Floating | Integer

QuotedStr.

 A quoted string is a delimited string with a double quote '"' as the delimiter.

QuotedStr  ::=  DelimitedStr('"')

UnsignedInt.

 An unsigned integer is a string of one or more digits.

UnsignedInt ::= Digit+

7.2 Syntactic Categories

The CGIF syntactic categories are defined by a context-free grammar that can be processed by a recursive-descent parser. Zero or more characters of white space (blanks or other nonprinting characters) are permitted between any two successive constituents of any grammar rule that defines a syntactic category.

Actor.

 An actor begins with "<" followed by a type. It continues with zero or more input arcs, a separator "|", zero or more output arcs, and an optional comment. It ends with ">".

Actor  ::=  "<" Type(N) Arc* "|" Arc* Comment? ">"

The arcs that precede the vertical bar are called input arcs, and the arcs that follow the vertical bar are called output arcs. The valence N of the actor type must be equal to the sum of the number of input arcs and the number of output arcs.

Arc.

 An arc is a concept or a bound label.

Arc  ::=  Concept | BoundLabel

BoundLabel.

 A bound label is a question mark "?" followed by an identifier.

BoundLabel  ::=  "?" Identifier

CG.

 A conceptual graph is a list of zero or more concepts, conceptual relations, actors, special contexts, or comments.

CG  ::=  (Concept | Relation | Actor | SpecialContext | Comment)*

The alternatives may occur in any order provided that any bound coreference label must occur later in the CGIF stream and must be within the scope of the defining label that has an identical identifier. The definition permits an empty CG, which contains nothing. An empty CG, which says nothing, is always true.

Concept.

 A concept begins with a left bracket "[" and an optional monadic type followed by optional coreference links and an optional referent in either order. It ends with an optional comment and a required "]".

Concept  ::=  "[" Type(1)? {CorefLinks?, Referent?} Comment? "]"

If the type is omitted, the default type is Entity. This rule permits the coreference labels to come before or after the referent. If the referent is a CG that contains bound labels that match a defining label on the current concept, the defining label must precede the referent.

In Figure 4, for example, the concept [Person: Mary] could be written in CGIF as [Person:'Mary'*x]; the coreferent concept [&top;] could be written [?x], and its implict type would be Entity.

Conjuncts.

 A conjunction list consists of one or more type terms separated by "&".

Conjuncts(N)  ::=  TypeTerm(N) ("&" TypeTerm(N))*

The conjunction list must have the same valence N as every type term.

CorefLinks.

 Coreference links are either a single defining coreference label or a sequence of zero or more bound labels.

CorefLinks  ::=  DefLabel | BoundLabel*

If a dominant concept node, as specified in Section 6.9, has any coreference label, it must be either a defining label or a single bound label that has the same identifier as the defining label of some co-nested concept.

DefLabel.

 A defining label is an asterisk "*" followed by an identifier.

DefLabel  ::=  "*" Identifier

The concept in which a defining label appears is called the defining concept for that label; a defining concept may contain at most one defining label and no bound coreference labels. Any defining concept must be a dominant concept as defined in Section 6.9.

Every bound label must be resolvable to a unique defining coreference label within the same context or some containing context. When conceptual graphs are imported from one context into another, however, three kinds of conflicts may arise:

1. A defining concept is being imported into a context that is within the scope of another defining concept with the same identifier.
2. A defining concept is being imported into a context that contains some nested context that has a defining concept with the same identifier.
3. Somewhere in the same module there exists a defining concept whose identifier is the same as the identifier of the defining concept that is being imported, but neither concept is within the scope of the other.

In cases (1) and (2), any possible conflict can be detected by scanning no further than the right bracket "]" that encloses the context into which the graph is being imported. Therefore, in those two cases, the newly imported defining coreference label and all its bound labels must be replaced with an identifier that is guaranteed to be distinct. In case (3), there is no conflict that could affect the semantics of the conceptual graphs or any correctly designed CG tool; but since a human reader might be confused by the similar labels, a CG tool may replace the identifier of one of the defining coreference labels and all its bound labels.

Descriptor.

 A descriptor is a structure or a nonempty CG.

Descriptor  ::=  Structure | CG

A context-free rule, such as this, cannot express the condition that a CG is only called a descriptor when it is nested inside some concept.

Designator.

 A designator is a literal, a locator, or a quantifier.

Designator  ::=  Literal | Locator | Quantifier

Disjuncts.

 A disjunction list consists of one or more conjunction lists separated by "|".

Disjuncts(N)  ::=  Conjuncts(N) ("|" Conjuncts(N))*

The disjunction list must have the same valence N as every conjunction list.

FormalParameter.

 A formal parameter is a monadic type followed by a optional defining label.

FormalParameter  ::=  Type(1) [DefLabel]

The defining label is required if the body of the lambda expression contains any matching bound labels.

Indexical.

 An indexical is the character "#" followed by an optional identifier.

Indexical  ::=  "#" Identifier?

The identifier specifies some implementation-dependent method that may be used to replace the indexical with a bound label.

IndividualMarker.

 An individual marker is the character "#" followed by an integer.

IndividualMarker  ::=  "#" UnsignedInt

The integer specifies an index to some entry in a catalog of individuals.

LambdaExpression(N).

A lambda expression begins with "(" and the keyword "lambda", it continues a signature and a conceptual graph, and it ends with ")".

LambdaExpression(N)  ::=  "(" "lambda" Signature(N) CG ")"

A lambda expression with N formal parameters is called an N-adic labda expression. The simplest example, represented "(lambda ())", is a 0-adic lambda expression with a blank CG.

Literal.

 A literal is a number or a quoted string.

Literal  ::=  Number | QuotedStr

Locator.

 A locator is a name, an individual marker, or an indexical.

Locator  ::=  Name | IndividualMarker | Indexical

Negation.

 A negation begins with a tilde "~" and a left bracket "[" followed by a conceptual graph and a right bracket "]".

Negation  ::=  "~[" CG "]"

A negation is an abbreviation for a concept of type Proposition with an attached relation of type Neg. It has a simpler syntax, which does not permit coreference labels or attached conceptual relations. If such options are required, the negation can be expressed by the unabbreviated form with an explicit Neg relation.

Quantifier.

 A quantifier consists of an at sign "@" followed by an unsigned integer or an identifier and an optional list of zero or more arcs enclosed in braces.

Quantifier  ::=  "@" (UnsignedInt | Identifier ("{" Arc* "}")?)

The symbol @some is called the existential quantifier, and the symbol @every is called the universal quantifier. If the quantifier is omitted, the default is @some.

Referent.

 A referent consists of a colon ":" followed by an optional designator and an optional descriptor in either order.

Referent  ::=  ":" {Designator?, Descriptor?}

Relation.

 A conceptual relation begins with a left parenthesis "(" followed by an N-adic type, N arcs, and an optional comment. It ends with a right parenthesis ")".

Relation  ::=  "(" Type(N) Arc* Comment? ")"
The valence N of the relation type must be equal to the number of arcs.

Signature.

 A signature is a parenthesized list of zero or more formal parameters separated by commas.

Signature  ::=  "(" (FormalParameter ("," FormalParameter)*)? ")"

SpecialConLabel.

 A special context label is one of five identifiers: "if", "then", "either", "or", and "sc", in either upper or lower case.

SpecialConLabel  ::=  "if" | "then" | "either" | "or" | "sc"

The five special context labels and the two identifiers "else" and "lambda" are reserved words that may not be used as type labels.

SpecialContext.

 A special context is either a negation or a left bracket, a special context label, an optional colon, a CG, and a right bracket.

SpecialContext  ::=  Negation | "[" SpecialConLabel ":"? CG "]"

Structure.

 A structure consists of an optional percent sign "%" and identifier followed by a list of zero or more arcs enclosed in braces.

Structure  ::=  ("%" Identifier)? "{" Arc* "}"

Type.

 A type is a type expression or an identifier other than the reserved labels: "if", "then", "either", "or", "sc", "else", "lambda".

Type(N)  ::=  TypeLabel(N) | TypeExpression(N)

A concept type must have valence N=1. A relation type must have valence N equal to the number of arcs of any relation or actor of that type. The type label or the type expression must have the same valence as the type.

TypeExpression.

 A type expression is either a lambda expression or a disjunction list enclosed in parentheses.

TypeExpression(N)  ::=  LambdaExpression(N) | "(" Disjuncts(N) ")"

The type expression must have the same valence N as the lambda expression or the disjunction list.

TypeLabel(N).

 A type label is an identifier.

TypeLabel(N)  ::=  Identifier

The type label must have an associated valence N.

TypeTerm.

 A type term is an optional tilde "~" followed by a type.

TypeTerm(N)  ::=  "~"? Type(N)

The type term must have the same valence N as the type.

As an example, the DF representation in Figure 1 was translated to LF, CGIF, and KIF in Section 5.1. Following is a translation of Figure 2 from DF to CGIF:

(Betw [Rock] [Place *x1] [Person]) (Attr ?x1 [Hard])

(Betw[Rock][Place*x1][Person])(Attr?x1[Hard])

[Rock *x1] [Place *x2] [Person *x3] (Betw ?x1 ?x2 ?x3)
[Hard ?x4] (Attr ?x2 ?x4)

Following is a translation of Figure 3 from DF to CGIF:

[Situation *x1 (Agnt [Plumber] [Carry *x2]) (Thme ?x2 [Pipe])]
(Imag ?x1 [Sound: %WAV"..."; The literal string encodes the audio. ])
(Imag ?x1 [Picture: %JPEG"..."; The literal string encodes the image. ])

Following is a translation of Figure 4 from DF to CGIF:

[Person: Tom *x1] [Believe *x2] (Expr ?x2 ?x1)
(Thme ?x2 [Proposition
   [Person: Mary *x3] [Want *x4]
   (Thme ?x4 [Situation
      (Agnt [Marry *x5] ?x3) (Thme ?x5 [Sailor]) ]) ])

7.3 Mapping AS to CGIF

1. Comments. No comments are represented in the abstract syntax. Therefore, the CGIF categories ActorComment, CGComment, ConComment, and RelComment do not correspond to anything in AS.
2. Lexical Categories. Since the AS features are independent of any notation or implementation, the lexical categories of Section 7.1, which are defined as character strings, do not have a direct mapping to AS. Some of them, such as WhiteSpace, do not correspond to anything in AS.
3. Noncontiguous Constituents. Every CGIF category defines a class of contiguous character strings. Some AS features, such as coreference sets, cannot be represented by a single contiguous string. Therefore, they must be mapped to a noncontiguous collection of strings, such as the defining and bound labels.

7.3.1 Conceptual Graph.

 Every conceptual graph (CG) is represented by a string of category CG.

• Every arc x of a CG is a pair consisting of a relation r and a concept cthat is linked to r. The Relation string that represents r contains the Arc string that represents x. That Arc string may either be the Concept string that represents cor a BoundLabel string whose identifier matches a DefLabel or BoundLabel in the Concept string that represents c.
• A CG string may contain Concept strings that represent concepts that are not linked to any conceptual relation.
• Three kinds of conceptual graphs are given distinguished names:
1. The blank is represented by an empty string or a string that contains nothing but strings of category WhiteSpace or CGComment.
2. A singleton is represented by a string of category CG that contains exactly one string of category Concept, but no strings of category Relation.
3. A star is represented by a string of category CG that contains exactly one string of category Relation. Every Concept string in the CG string must represent one of the concepts attached to the conceptual relation of the star graph.

7.3.2 Concept.

 Every concept cis represented by a Concept string that contains a Type string that represents the concept type of c and a Referent string that represents the referent of c.

7.3.3 Conceptual Relation.

 Every conceptual relation r is represented by a Relation string or an Actor string. The relation type of r is the RelTypeLabel or the LambdaExpression contained in the Relation string or the Actor string. The valence of r is the valence of the RelTypeLabel or the LambdaExpression.

• The number of Arc strings in the Relation string or the Actor string is equal to the valence of r.
• The signature of r is the signature of the RelTypeLabel or the LambdaExpression contained in the Relation string or the Actor string.

A conceptual relation that is represented by an Actor string may have side effects that are not represented in the abstract syntax or the translation to predicate calculus defined in Chapter 8.

7.3.4 Lambda Expression.

 Every lambda expression e is represented by a LambdaExpression string that contains n FormalParameter strings that represent the formal parameters of e and a CG string that represents the body of e.

• For each i from 1 to n, the i-th formal parameter of e is represented by the i-th FormalParameter string.
• The signature of e is the sequence of Type strings contained in the FormalParameter strings.

7.3.5 Concept Type.

 Every type hierarchy T may be represented by a concept of type TypeHierarchy that contains a nested CG that defines the concept type labels of T and the partial ordering over T:

TypeHierarchy  ::=  "[" "TypeHierarchy"
     (TypeDefinition | TypeLabelOrdering)* "]"

A type definition is a star graph containing a conceptual relation of type Def that relates a type label to a lambda expression:

TypeDefinition  ::= "(" "Def"
     "[" "TypeLabel" "\"" ConTypeLabel "\"" "]"
     "[" "LambdaExpression" "\"" LambdaExpression "\"" "]" ")"

A type label ordering is a star graph containing a conceptual relation of type EQ, GT, or LT that relates two type labels:

TypeLabelOrdering  ::= "(" ("EQ" | "GT" | "LT")
     "[" "TypeLabel" "\"" ConTypeLabel "\"" "]"
     "[" "TypeLabel" "\"" ConTypeLabel "\"" "]" ")"

For two type labels s and t, the type label ordering has a conceptual relation of type EQ iff s=t, of type GT iff s>t, and of type LT iff s<t.

The type definitions and type label orderings that define a type hierarchy must obey the following constraints:

• A type label that does not appear in a type definition is said to be primitive.
• Two primitive type labels are Entity and Absurdity. Every type hierarchy contains the star graph

(GT [TypeLabel "Entity"] [TypeLabel "Absurdity"]).

• A type label that appears in a type definition is said to be defined, and no type label may appear in more than one type definition.

For more concise storage and transmission, multiple star graphs for the type label ordering may be abbreviated by using a collection as defined in Section 8.2. As an example, the following star graph asserts that the type label "Entity" is related to each type label in the collection by the relation GT:

(GT [TypeLabel "Entity"]
    [TypeLabel @Col{"Physical", "Abstract", "Independent",
        "Relative", "Mediating", "Continuant", "Occurrent"}])]

The translation rules in Section 8.2 would expand this star graph to seven separate star graphs -- one for each type label in the collection.

7.3.6 Relation Type.

 Every relation hierarchy R may be represented by a concept of type RelationHierarchy that contains a nested CG that defines the relation type labels of R and the partial ordering over R:

RelationHierarchy  ::=  "[" "RelationHierarchy"
     (RelationDefinition | ValenceSpec | RelationLabelOrdering)* "]"

A relation definition is a star graph containing a conceptual relation of type Def that relates a relation label to a lambda expression:

RelationDefinition  ::= "(" "Def"
     "[" "RelationLabel" "\"" RelTypeLabel "\"" "]"
     "[" "LambdaExpression" "\"" LambdaExpression "\"" "]" ")"

A valence specification is a star graph containing a conceptual relation of type Has that relates a relation label to its valence:

ValenceSpec  ::= "(" "Has"
     "[" "RelationLabel" "\"" RelTypeLabel "\"" "]"
     "[" "Valence" Integer "]" ")"

A relation label ordering is a star graph containing a conceptual relation of type EQ, GT, or LT that relates two type labels:

RelationLabelOrdering  ::= "(" ("EQ" | "GT" | "LT")
     "[" "RelationLabel" "\"" RelTypeLabel "\"" "]"
     "[" "RelationLabel" "\"" RelTypeLabel "\"" "]" ")"

For two relation labels r and s, the relation label ordering has a conceptual relation of type EQ iff r=s, of type GT iff r>s, and of type LT iff r<s.

The most general relation type of valence n would be defined by a lambda expression (lambda(Entity,...,Entity)), in which the signature is a list of n concepts of type Entity. A relation of that type would always be true when linked to n concepts of any type.

The relation definitions, valence specifications, and relation label orderings that define a relation hierarchy must obey the following constraints:

• Every primitive relation label must have exactly one valence specification and no relation definition.
• Every defined relation label must have exactly one relation definition and no valence specification.

For more concise storage and transmission, multiple star graphs for relation label orderings and valence specifications may be abbreviated by using collections. As an example, the following star graph asserts that each of the four type labels in the collection has the valence 2:

(Has [TypeLabel @Col{"EQ", "GT", "LT", "Has"}] [Valence 2])

The translation rules in Section 8.2 would expand this star graph to four separate star graphs -- one for each type label in the collection.

7.3.7 Referent.

 The referent of a concept is represented by a quantifier string and a designator string.

• A quantifier string is one of the following two kinds:
1. Existential. An existential quantifier is represented by the empty string "" or by the string "@exist".
2. Defined. A defined quantifier is represented by the character "@" followed by an identifier or expression that is defined as a quantifier in Section 8.2.
• A designator is one of three kinds:
1. Literal. A literal is represented by a Literal string.
2. Locator. A locator is represented by an Indexical string, an IndividualMarker string, or a Name string.
3. Descriptor. A descriptor is represented by a CG string containing at least one Concept string or Relation string.

7.3.8 Context.

 A context is represented by a SpecialContext string or by a Concept string that contains a CG string containing at least one Concept string or Relation string.

7.3.9 Coreference Set.

 Every coreference set C is represented by an identifier i that matches the coreference labels of every Concept string that represent concepts in C.

• One of the dominant nodes d in C shall be selected as the defining node of C, and the Concept string that represents d shall contain the defining label *i and no other coreference labels.
• Every Concept string that represents a concept in C other than d shall contain a bound label ?i and no defining labels.
• No Concept string that represents any dominant concept in C may contain a coreference label that does not match i.
• Any Concept string that represents a nondominant concept in C may contain one or more bound labels other than ?i.
• If d is the only concept in C, the defining label *i is optional and may be omitted.
• No concept within the scope of d that is not in C may be represented by a Concept string that contains a coreference label that matches i.

7.3.10 Module.

 A moduleis represented by a context of type Module, which contains three contexts whose types are TypeHierarchy, CatalogOfIndividuals, and Assertion. Its syntax is defined by the following translation rule (see Annex B.2):

KB  ::=  "[" "Module" ":"
           { "[" "TypeHierarchy" ":" CG.T "]",
             "[" "CatalogOfIndividuals" ":" CG.C "]",
             "[" "Assertion" ":" CG.O "]" } "]"

When the pattern part of this rule matches a CGIF string that represents a module, the CGs used as designators of the four nested concepts are assigned to the variables T, R, C, and O. Those CGs must obey the following constraints:

1. Type hierarchy. The conceptual graph T contains one concept of the form "[ConTypeLabel:" Identifier.t DefLabel "]" for each type label t. To specify the partial ordering, T also contains a collection of star graphs of the form "(PSbt" BoundLabel BoundLabel ")", which specifies that the first bound label refers to a type label that has as proper subtype (PSbt) the type label referred to by the second bound label. For each defined type label, there is a star graph of the form "(Def" BoundLabel "[LambdaExpression:" "\"" LambdaExpression.e "\"" "])", which specifies that the bound label refers to a type label that is is defined (Def) by the quoted lambda expression in the following concept.
2. Relation hierarchy. The conceptual graph R contains one concept of the form "[RelTypeLabel:" Identifier.r DefLabel "]" for each relation type label r. To specify the partial ordering, R also contains a collection of star graphs of the form "(PSbt" BoundLabel BoundLabel ")", which specifies that the first bound label refers to a relation type label that has as proper subtype the relation type label referred to by the second bound label. For each defined type label, there is a star graph of the form "(Def" BoundLabel "[LambdaExpression:" "\"" LambdaExpression.e "\"" "])", which specifies that the bound label refers to a relation type label that is is defined (Def) by the quoted lambda expression in the following concept.
3. Catalog of individuals. A concept whose designator is a conceptual graph g that contains global information about the individuals identified by individual markers in B. For each individual marker i that occurs in any concept of B, there is exactly one concept c immediately nested in g whose designator is i. The graph g may also contain other concepts and conceptual relations that describe the individuals in the catalog and the relationships among them.
4. Outermost context. A context A called the outermost context of B whose type label is Assertion and whose nested CG contains only type labels in T, relation labels in R, and individual markers in C.

Although CGIF requires that every bound coreference label be preceded by a matching defining coreference label, there is no such restriction on the type labels and the relation labels. Therefore, the definitions of type and relation labels may be recursive or mutually recursive. Any implementation of CGIF must be prepared to allocate internal storage space for type and relation labels before their definitions and partial ordering have been specified.

Comment.

The CGs T and R specify the possible type and relation labels that may appear in any concept in the module together with their definitions and the partial orderings of the type and relation hierarchies. The CG C catalogs all the entities that represent individuals that may be explicitly referenced in the module; it may also assert some background knowledge about those individuals. All other assertions that are known or assumed to be true in the current module are stated by the CG O.

Since a module is also a concept, it may be linked to conceptual relations in a conceptual graph that makes a statement about the module, the CGs nested inside it, and the entities those CGs may refer to. Such a graph could be nested in the outermost context of another module, which would then be a metaknowledge base about the nested module. Modules may be nested to any depth; a metamodule may contain assertions about knowledge bases nested inside itself, but no module may contain references to a module in which it is nested.

8 Extended Syntax

8.1 Type Coercions

8.2 Special Contexts

The first two special context labels are "If" and "Then", which are used to represent material implication. The syntactic category IfThen is defined as a context with the label "If" whose designator is any CG and a context with the label "Then":

IfThen  ::=  "[" "If" CG "[" "Then" CG "]" "]"

TrIfThen  ::=  "[" "If" CG.x "[" "Then" CG.y "]" "]"
           =>  "~[" x "~[" y "]" "]"

As an example, the following CGIF string represents the sentence If Sam has a car, then Sam drives the car:

[If (Has [Person 'Sam'] [Car]
    [Then [Drive *x] (Agnt ?x [Person 'Sam']) (Thme ?x [Car #]) ]]

~[ (Has [Person 'Sam'] [Car]
    ~[ [Drive *x] (Agnt ?x [Person 'Sam]) (Thme ?x [Car #]) ]]

The Either and Or contexts represent disjunction. The syntactic category EitherOr is defined as a context that has the special label "Either" that contains a conceptual graph and zero or more contexts with the special label "Or":

EitherOr  ::=  "[" "Either" CG
                   ("[" "Or" CG "]")* "]"

TrEither  ::=  "[" "Either" CG.x
                   ("[" "Or" CG "]")*.y "]"
           =>  "~[" x TrOrs(y) "]"

TrOrs  ::=  ("[" "Or" CG.x "]")?.y String.z RightEnd
        =>  (y="" ? "" | "~[" x "]" TrOrs(z))

As an example, the following CGIF string has two nested Or contexts to represent the sentence Either Sam has a car, or Sam rides a bus:

[Either
   [Or (Has [Person Sam] [Car]) ]
   [Or [Ride *x] (Agnt ?x [Person Sam]) (Inst ?x [Bus]) ]]

~[
   ~[ (Has [Person Sam] [Car]) ]
   ~[ [Ride *x] (Agnt ?x [Person Sam]) (Inst ?x [Bus]) ]]

[Either [Cat *x]
   [Or (On ?x [Mat]) ]
   [Or (Agnt [Eat] ?x) ]
   [Or [Chase *y] (Agnt ?y ?x) (Thme ?y [Mouse]) ]]

[Cat *x]
[Either
   [Or (On ?x [Mat]) ]
   [Or (Agnt [Eat] ?x) ]
   [Or [Chase *y] (Agnt ?y ?x) (Thme ?y [Mouse]) ]]

8.3 Defined Quantifiers

As an example, consider the following CGIF representation the sentence Every cat is on a mat:

(On [Cat @every] [Mat])

~[ [Cat: *_5219]
  ~[ (On ?_5219 [Mat]) ]]

Following are some other constructions that can be introduced by translation rules:

• Collective designator. In the concept [Candle: {*}@50], the generic set symbol {*} is a collective designator that represents a set of unspecified elements of type Candle, and the quantifier @50 is the count or cardinality of the set of candles.
• Set and sequence. In the concept [Person: {Bill, Mary, Sam}], the collective designator represents a set of three people, and the order is not significant. In [Person: <Bill, Mary, Sam>], the collective designator represents a sequence of the same three people, but the order is significant: Bill is the first, Mary is second, and Sam is third.
• Quantifier. The existential quantifier, which is represented by a blank, is the default. The universal quantifier is represented by the character "&forall;", as in [Person: &forall;], read every person. A count is represented by the symbol @ followed by an integer, as in [Person: {*}@5], read five persons. A measure is represented by the symbol @ followed by a number and a measuring unit, as in [Interval: 15 sec], read an interval of 15 seconds.
• Collective quantifier. The generic set symbol {*} and the generic sequence symbol "<*>" are collective designators, which may be combined with a quantifier that indicates the number of elements in the set or sequence: [Farmer: {*}] may be read a set of farmers; [Letter: <*>@3] may be read a sequence of three letters. The referent {*}&forall; implies a set of all elements of the type specified in the type field of the concept, as in [Farmer: {*}&forall;], read the set of all farmers.
• Lambda expressions as types. Since type labels are synonyms for lambda expressions, a lambda expression may occur anywhere that a type label may occur. Consider the following concept:

[ [Farmer: λ]->(Loc)->[State: Maine]: {*}∀].

The type field contains a lambda expression for farmer located (Loc) in the state of Maine, and the referent field contains the generic set symbol {*} and a universal quantifier &forall;. Altogether, this concept may be read the set of all farmers located in the state of Maine.

[TrailerTruck: ¬]->(Part)->[Wheel: {*}@>18].

¬[ [TrailerTruck]->(Part)->[Wheel: {*}@>18] ].

Precedence levels for quantifiers.

(∀x:Woman)(∃y:Man)married(x,y).

(∃y:Man)(∀x:Woman)married(x,y).

In EGs and CGs, the scope is normally shown by context enclosures, which correspond to the parentheses in predicate calculus. To reduce the number of contexts, another way of showing scope is to assume precedence levels for the various kinds of quantifiers. By convention, the universal quantifier &forall; has higher precedence than the existential quantifiers in the same context. With that convention, the two sentences may be represented by the following conceptual graphs:

(Past)->[Situation: [Woman: &forall;]<-(Agnt)<-[Marry]->(Thme)->[Man] ].

[Man: *x]  (Past)->[Situation: [Woman: &forall;]<-(Agnt)<-[Marry]->(Thme)->[?x] ].

In English, scope is often shown by special words and stylistic conventions. The word certain, in the sentence Every woman married a certain man, suggests that the existential quantifier for a certain man has higher precedence than the universal quantifier for every woman. Therefore, the CG symbol @certain may be defined as an existential quantifier with a higher precedence than &forall;:

(Past)->[ [Woman: &forall;]<-(Agnt)<-[Marry]->(Thme)->[Man: @certain] ].

• High precedence. The symbol @certain in the referent field represents an existential quantifier whose scope includes any universal quantifier in the same context.
• Middle precedence. The universal quantifier &forall; has lower precedence than @certain, but it has higher precedence than the existential quantifier shown by a blank or by the character "&exist;".
• Low precedence. The basic existential quantifier, represented by &exist; or by a blank, has the lowest precedence. It is within the scope of all other quantifiers in the same context.

9 Logical Foundations

9.1 Translation to Predicate Calculus

[Go *x] (Agnt ?x [Person: John]) (Dest ?x [City: Boston]) (Inst ?x [Bus])

[Go *x] [Person: John *y] [City: Boston *z] [Bus *w]
(Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?z)

(∃x:Go)(∃y:Person)(∃z:City)(∃w:Bus)
   (Name(y,'John') ∧ Name(z,'Boston') ∧
      Agnt(x,y) ∧ Dest(x,z) ∧ Inst(x,w))

(exists ((?x Go) (?w Bus))
        (and (Person John) (City Boston)
             (Agnt ?x John) (Dest ?x Boston) (Inst ?x ?w)))

The translation from CGIF to predicate calculus is defined by the function &phi;. If u is any CG, then &phi;(u) is the corresponding predicate calculus formula. As examples, following are five English sentences and their represetations in CGIF, predicate calculus, and KIF:

1. Every cat is on a mat.

(On [Cat: @every] [Mat])

(∀x:Cat)(∃y:Mat)On(x,y)

(forall (?x cat) (exists (?y mat) (on ?x ?y)))

2. It is false that every dog is on a mat.

~[(On [Dog: @every] [Mat])]

~(∀x:Dog)(∃y:Mat)on(x,y)

(not (forall (?x dog) (exists (?y mat) (on ?x ?y))))

3. Some dog is not on a mat.

[Dog *x]  ~[(On ?x [Mat])]

(∃x:Dog)~(∃y:Mat)On(x,y)

(exists (?x dog) (not (exists (?y mat) (on ?x ?y))))

4. Either the cat Yojo is on a mat, or the dog Macula is running.

[Either
   [Or (On [Cat: Yojo] [Mat])]
   [Or (Agnt [Run] [Dog: Macula])] ]

((∃x:Cat)(∃y:Mat)(Name(x,'Yojo') ∧ On(x,y)) ∨
   ((∃z:Dog)(∃w:Run)(Name(z,'Macula') ∧ Agnt(w,z)))

(or (exists (?y mat) (and (cat Yojo) (on Yojo ?y)))
    (exists (?w run) (and (dog Macula) (agnt ?w Macula))))

5. If a cat is on a mat, then it is happy.

[If (On [Cat *x] [Mat])
   [Then (Attr ?x [Happy])] ]

(∀x:Cat)(∀y:Mat)(On(x,y) &implies;
   (∃z:Happy)Attr(x,z))

(forall ((?x cat) (?y mat))
        (=> (on ?x ?y)
            (exists (?z happy) (attr ?x ?z))))

9.2 Canonical Formation Rules

The first two rules, which are illustrated in Figure 5, are copy and simplify. At the top is a CG for the sentence "The cat Yojo is chasing a mouse." The down arrow represents the copy rule. One application of the rule copies the Agnt relation, and a second application copies the subgraph ->(Thme)->[Mouse]. Both copies are redundant, since they add no new information. The up arrow represents two applications of the simplify rule, which performs the inverse operation of erasing redundant copies. The copy and simplify rules are called equivalence rules because any two CGs that can be transformed from one to the other by any combination of copy and simplify rules are logically equivalent. The two formulas in predicate calculus that are derived from the CGs in Figure 5 are also logically equivalent. The top CG maps to the following formula:

• (&exist;x:Cat)(&exist;y:Chase)(&exist;z:Mouse)(name(x,'Yojo') &and; agnt(y,x) &and; thme(y,z)),

• (&exist;x:Cat)(&exist;y:Chase)(&exist;z:Mouse)(&exist;w:Mouse)(name(x,'Yojo') &and; agnt(y,x) &and; agnt(y,x) &and; thme(y,z) &and; thme(y,w) &and; z=w).

Figure 5. Copy and simplify rules

Figure 6 illustrates the restrict and unrestrict rules. At the top is a CG for the sentence "A cat is chasing an animal." By two applications of the restrict rule, it is transformed to the CG for "The cat Yojo is chasing a mouse." The first step is a restriction by referent of the concept [Cat], which represents some indefinite cat, to the more specific concept [Cat: Yojo], which represents an individual cat named Yojo. The second step is a restriction by type of the concept [Animal] to a concept of the subtype [Mouse]. Two applications of the unrestrict rule perform the inverse transformation of the bottom graph to the top graph. The restrict rule is called a specialization rule, and the unrestrict rule is a generalization rule. The more specialized graph implies the more general one: if the cat Yojo is chasing a mouse, it follows that a cat is chasing an animal. The same implication holds for the corresponding formulas in predicate calculus. The more general formula

• (&exist;x:Cat)(&exist;y:Chase)(&exist;z:Animal)(agnt(y,x) &and; thme(y,z))

• (&exist;x:Cat)(&exist;y:Chase)(&exist;z:Mouse)(name(x,'Yojo') &and; agnt(y,x) &and; agnt(y,x) &and; thme(y,z)).

Figure 7 illustrates the join and detach rules. At the top are two CGs for the sentences "Yojo is chasing a mouse" and "A mouse is brown." The join rule overlays the two identical copies of the concept [Mouse] to form a single CG for the sentence "Yojo is chasing a brown mouse." The detach rule performs the inverse operation. The result of join is a more specialized graph that implies the one derived by detach. The same implication holds for the corresponding formulas in predicate calculus. The conjunction of the formulas for the top two CGs

• ((&exist;x:Cat)(&exist;y:Chase)(&exist;z:Mouse)(name(x,'Yojo') &and; agnt(y,x) &and; thme(y,z)) &and; ((&exist;w:Mouse)(&exist;v:Brown)attr(w,v))

• (&exist;x:Cat)(&exist;y:Chase)(&exist;z:Mouse)(&exist;v:Brown)(name(x,'Yojo') &and; agnt(y,x) &and; thme(y,z) &and; attr(z,w)).

Although the canonical formation rules are easy to visualize, the formal specifications require more detail. They are most succinct for the simple graphs, which are CGs with no contexts, no negations, and no quantifiers other than existentials. The following specifications, stated in terms of the abstract syntax, can be applied to a simple graph u to derive another simple graph w.

1. Equivalence rules. The copy rule copies a graph or subgraph. The simplify rule performs the inverse operation of erasing a copy. Let v be any subgraph of a simple graph u; v may be empty or it may be all of u.
• Copy. The copy rule makes a copy of any subgraph v of u and adds it to u to form w. If cis any concept of v that has been copied from a concept d in u, then cmust be a member of exactly the same coreference sets as d. Some conceptual relations of v may be linked to concepts of u that are not in v; the copies of those conceptual relations must be linked to exactly the same concepts of u.
• Simplify. The simplify rule is the inverse of copy. If two subgraphs v₁ and v₂ of u are identical, they have no common concepts or conceptual relations, and corresponding concepts of v₁ and v₂ belong to the same coreference sets, then v₂ may be erased. If any conceptual relations of v₁ are linked to concepts of u that are not in v₁, then the corresponding conceptual relations of v₂ must be linked to exactly the same concepts of u, which may not be in v₂.
2. Specialization rules. The restrict rule specializes the type or referent of a single concept node. The join rule merges two concept nodes to a single node. These rules transform u to a graph w that is more specialized than u.
• Restrict. Any concept or conceptual relation of u may be restricted by type by replacing its type with a subtype. Any concept of u with a blank referent may be restricted by referent by replacing the blank with some other existential referent.
• Join. Let cand d be any two concepts of u whose types and referents are identical. Then w is the graph obtained by deleting d, adding cto all coreference sets in which d occurred, and attaching to call arcs of conceptual relations that had been attached to d.
3. Generalization rules. The unrestrict rule, which is the inverse of restrict, generalizes the type or referent of a concept node. The detach rule, which is the inverse of join, splits a graph in two parts at some concept node. The last two rules transform u to a graph w that is a generalization of u.
• Unrestrict. Let cbe any concept of u. Then w may be derived from u by unrestricting ceither by type or by referent: unrestriction by type replaces the type label of cwith some supertype; and unrestriction by referent erases an existential referent to leave a blank.
• Detach. Let cbe any concept of u. Then w may be derived from u by making a copy d of c, detaching one or more arcs of conceptual relations that had been attached to c, and attaching them to d.

For nested contexts, the formation rules depend on the number of negations. A positive context (sign +) is nested in an even number of negations (possibly zero). A negative context (sign -) is nested in an odd number of negations.

• Zero negations. A context that has no attached negations and is not nested in any other context is defined to be positive.
• Negated context. The negation relation (Neg) or its abbreviation by the ~ or ¬ symbol reverses the sign of any context it is attached to: a negated context contained in a positive context is negative; a negated context contained in a negative context is positive.
• Scoping context. A context C with the type label SC and no attached conceptual relations is a scoping context, whose sign is the same as the sign of the context in which it is nested.

1. Equivalence rules.
• If v is a CG in the context C, then let w be the graph obtained by performing a copy or simplify rule on v.
• A negated context whose referent is another negated context is called a double negation. If u is a double negation that includes the graph v, then let w be the graph obtained by replacing u with a scoping context around v:

~[ ~[v]]  =>  [SC: v].

A double negation or a scoping context around a conceptual graph may be drawn or erased at any time. If v is a conceptual graph, the following three forms are logically equivalent:

~[ ~[v]],  [SC: v],  v.

2. Specialization rules.
• If C is positive, then let w be the result of performing any specialization rule in C.
• If C is negative, then let w be the result of performing any generalization rule in C.
3. Generalization rules.
• If C is positive, then let w be the result of performing any generalization rule in C.
• If C is negative, then let w be the result of performing any specialization rule in C.

9.3 Rules of Inference

• Equivalence rules. The equivalence rules may change the appearance of a graph, but they do not change its logical status. If a CG u is converted to a CG v by these rules, then u implies v, and v implies u.
• Specialization rules:. The specialization rules transform a CG u to another CG v that is logically more specialized: v implies u.
• Generalization rules. The generalization rules transform a CG u to another CG v that is logically more generalized: u implies v.

• Erasure. In a positive context, any graph u may be replaced by a generalization of u; in particular, u may be erased (i.e. replaced by the blank, which is a generalization of every CG).
• Insertion. In a negative context, any graph u may be replaced by a specialization of u; in particular, any graph may be inserted (i.e. it may replace the blank).
• Iteration. If a graph u occurs in a context C, another copy of u may be drawn in the same context C or in any context nested in C.
• Deiteration. Any graph u that could have been derived by iteration may be erased.
• Equivalence. Any equivalence rule (copy, simplify, or double negation) may be performed on any graph or subgraph in any context.

Coreference links.

Lambda conversions.

• Type expansion. Let g be a conceptual graph containing a concept cthat has a defined type t and an existential referent (i.e. a blank or &exist; as its quantifier). Then the operation of type expansion performs the following transformations on g:
1. The definition of t must be a monadic lambda expression whose body is a conceptual graph b and whose formal parameter p is a concept of b. Let the signature of t be the sequence (s), where s is the type of p.
2. Remove the type t from the concept cof g, and replace it with s.
3. Remove the &lambda; marker from the concept p, and replace it with the designator of c.
4. At this point, the concepts cand p should be identical. Combine the graphs g and b by joining p to c.
• Relational expansion. Let g be a conceptual graph containing an n-adic relation r that has a defined type t. Then the operation of relational expansion performs the following transformations on g:
1. The definition of t must be an n-adic lambda expression whose body is a conceptual graph b and whose formal parameters <p₁,...,p_n> are concepts of b. Let the signature of t be the sequence (s₁,...,s_n), where each s_i is the type of p_i.
2. Remove the relation r from g, and detach each arc i of r from the concept c_i of g.
3. Remove the &lambda; marker from each parameter p_i, and replace it with the designator of c_i.
4. For each i from 1 to n, restrict the types of c_i and p_i to their maximal common subtypes. Then combine the graphs g and b by joining each p_i to c_i.

9.4 Conformance Levels

Annex A (Informative) Presentation Formats

Unlike the abstract form, the concrete notations must deal with the limitations of some physical medium: material such as paper, plastic, or glass; images displayed on a two-dimensional surface or in a three-dimensional space; or structures of bits and pointers in computer storage. The physical medium may introduce features that are not part of the formal definition:

• Location. Every concept and relation node in a concrete representation must have some location, described either by spatial coordinates or by some kind of address.
• Visual phenomena. The nodes of a concrete representation may differ in size, position, brightness, and color.
• Storage limitations. When graphs and collections of graphs become large, they may exceed the size of a sheet of paper, a display screen, or computer storage. Various techniques may be used to move, display, scroll, or zoom in and out of graphs.

A.1 Display Form

1. Concept nodes are drawn as rectangles, which are also called boxes.
2. Conceptual relation nodes are drawn as circles, ovals, or ellipses; they may be called circles, even though they may be elongated to ovals or ellipses to accommodate long identifiers or expressions.
3. The arcs that link a conceptual relation node to a concept node are drawn as solid lines, preferably straight. If necessary, the arcs may cross other arcs, coreference links, and nodes; but to minimize the crossing, the arcs may be curved or bent.
4. The size and position of the nodes, the orientation of the arcs, and the point where an arc is attached to a node has no semantic significance. Sizes and positions may be changed to enhance readability or save space.
5. To distinguish the arcs of an n-adic relation, an integer from 1 to n is drawn next to each arc. For improved readability, other conventions for distinguishing the arcs are permissible:
• For monadic relations, the integer 1 is optional. It may either be omitted entirely or be replaced by an arrowhead pointing away from the relation.
• For dyadic relations, the integer 1 may be replaced by an arrowhead pointing toward the relation, and the integer 2 may be replaced by an arrowhead pointing away from the relation.
• For n-adic relations where n>2, the integer n may be replaced by an arrowhead pointing away from the relation. For the arcs from 1 to n-1, each arc may have both an integer and an arrowhead pointing toward the relation
• If a dyadic relation is declared to be symmetric, the integers or arrowheads are optional.
• If an n-adic relation where n>2 is declared to be symmetric in the arcs from 1 to k for 1<k<n, the integers from 1 to k may be replaced by arrowheads pointing toward the relation.
• If an n-adic relation is declared to be functional, its n-th arc may be drawn as a double line with an arrowhead pointing away from the relation.
• An arrowhead on an arc may be placed either in the middle of an arc or at the end toward which it points.
6. The coreference links that connect concepts to concepts are drawn as dotted or dashed lines that are lighter in weight than the arcs that link conceptual relations to concepts. Any coreference link may be replaced by coreference labels with the same conventions used for CGIF.
7. The type and referent fields of a concept box are separated by a vertical or horizontal line of two or more dots; a vertical line of exactly two dots represents the colon character ":", which is the normal separator in LF.
8. When the separator is a vertical line, the type field is on the left, and the referent field is on the right. When the separator is a horizontal line, the type field is above, and the referent field is below the line. Figure 8 shows the five possible orientations of the type and referent fields. The form in the upper left-hand corner is the preferred one; the others are used to provide more space for large type or referent expressions.


Figure 8. Five possible orientations of the type and referent fields



9. The contents of the type and referent fields, which are defined in Sections 6.5 and 6.7, are the same for both the display form and the linear form.
10. A context drawn in DF may contain a nested CG in DF or LF. A context in LF, however, may not contain a nested CG in DF.
11. To minimize line crossing, any concept node may be split in two or more nodes in the same context. The first node contains all the type and referent information of the original concept node. It must be marked with a defining label such as *x or a bound label such as ?x. All the other nodes may be drawn as boxes containing nothing but a corresponding bound label such as [?x]. Any coreference links attached to the original node must remain attached to the first node of the split. Any arc of a conceptual relation attached to the original node must be attached to one of the split nodes, but which one is semantically irrelevant.

A.2 Linear Form (LF)

• A CG is either a ConceptBranch or a Relation followed by either a ConceptLink or a ConceptList:

CG  ::=  ConceptBranch | Relation (ConceptLink | ConceptList)

• A ConceptBranch is a Concept, which is optionally followed by either a RelationLink or a RelationList:

ConceptBranch  ::=  Concept (RelationLink | RelationList)?

• A RelationBranch is a Relation, which is optionally followed by either a ConceptLink or a ConceptList:

RelationBranch  ::=  Relation (ConceptLink | ConceptList)?

• A ConceptLink is an Arc followed by a ConceptBranch:

ConceptLink  ::=  Arc ConceptBranch

• A RelationLink is an Arc followed by a RelationBranch:

RelationLink  ::=  Arc RelationBranch

• A ConceptList is a BeginLinks marker, a ConceptLink, zero or more pairs of LinkSep and ConceptLink, and an EndLinks marker:

ConceptList  ::=  BeginLinks ConceptLink (LinkSep ConceptLink)* EndLinks

• A RelationList is a BeginLinks marker, a RelationLink, zero or more pairs of LinkSep and RelationLink, and an EndLinks marker:

RelationList  ::=  BeginLinks RelationLink (LinkSep RelationLink)* EndLinks

• A Concept is a BeginConcept marker, a Type, an optional pair of a FieldSep and a Referent, and an EndConcept marker:

Concept  ::=  BeginConcept Type (FieldSep Referent)? EndConcept

• A Relation is a BeginRelation marker, a Type, and an EndRelation marker:

Relation  ::=  BeginRelation Type EndRelation

• An Arc is an optional Integer followed by either a LeftArc or a RightArc:

Arc  ::=  Integer? (LeftArc | RightArc)

• A Type is either a TypeLabel or a LambdaExpression:

Type  ::=  TypeLabel | LambdaExpression

Annex B (Normative) Metalevel Conventions

B.1 Extended BNF Rules

EBNFRule  ::=  CategorySymbol DefiningMarker DefiningExpression

Category.

A class of strings named by an identifier called a category symbol. Every category is a metalevel category, a lexical category, or a syntactic category.

DefiningExpression.

A defining expression is a sequence of one or more terms separated by a concatenator (white space) or an alternator (vertical bar with optional white space on either side).

DefiningExpression  ::=  Term
     ((WhiteSpace | WhiteSpace? "|" WhiteSpace?) Term)*

The concatenator indicates sequence: each term must match a string of the corresponding type in the order in which they occur. The alternator, which may include optional white space on either side, indicates options: either the term on its right or the term on its left, but not both, must match a string of the corresponding type. If a defining expression contains both concatenators and alternators, the concatenators have higher precedence (tighter binding) than the alternators.

DefiningMarker.

A defining marker is a string consisting of two colons and an equal sign "::=" with optional white space on either side.

DefiningMarker  ::=  WhiteSpace? "::=" WhiteSpace?

In an EBNF rule, it indicates that the category on its left is defined by the expression on its right.

MetalevelCategory.

A metalevel category is any category whose symbol is defined in Annex B of ISO nnn-n. Metalevel categories are used only to define the syntax of EBNF rules or translation rules.

LexicalCategory.

A lexical category is any category whose symbol is defined in Section 7.1 of ISO nnn-n. Lexical categories may be used in EBNF rules or translation rules.

Set.

A set is collection of one or more defining expressions enclosed in braces and separated by commas. The commas and the braces may have optional white space on either side.

Set  ::=  "{" DefiningExpression ("," DefiningExpression)* "}"

Each defining expression in the set must match exactly one string, but the strings they match may occur in any order.

SyntacticCategory.

A syntactic categoryis a category whose symbol appears on the left side of some EBNF rule in Section 7.2 of ISO nnn-n.

Term.

A term is a category symbol, a literal string, a set, or a defining expression enclosed in parentheses followed by an optional iterator "*", repeater "+", or option "?" symbol.

Term  ::=  (CategorySymbol | Literal | Set | "(" DefiningExpression ")" )
           ("*" | "+" | "?")?

The iterator indicates zero or more occurrences of the preceding string, the repeater indicates one or more occurrences, and the option indicates zero or one occurrence.

B.2 Translation Rules

TranslationRule  ::=  RuleName "::=" DefiningExpression "=>" Target

Conditional.

A conditional is a translation sequence and test followed by a true option and a false option.

Conditional  ::=  "(" TranSequence Test "?" TranSequence ":" TranSequence ")"

The value of the first translation sequence is tested for equality "=" or nonequality "!=". If the test is true, the value of the conditional is the value of the second translation sequence; otherwise, it is the value of the third translation sequence.

DefiningExpression.

A defining expression of a translation rule is a sequence of one or more translation terms separated by a concatenator (white space) or an alternator (vertical bar with optional white space on either side).

DefiningExpression  ::=  TranTerm
     ((WhiteSpace | WhiteSpace? "|" WhiteSpace?) TranTerm)*

Any defining expression of an EBNF rule as specified in Section B.1 is valid in a translation rule. The only difference is that the translation terms may have an optional variable assignment and an optional test.

GenerationTerm.

A generation term is a literal, a variable, a rule call, or a conditional.

GenerationTerm  ::=  Literal | Variable | RuleCall | Conditional

The value of the generation term is the value of the literal, variable, rule call, or conditional.

LeftEnd.

A left end is an empty string that is assumed to precede any string. In a defining expression, the left end matches the start of any source string, and its value is the empty string "".

RightEnd.

A right end is an empty string that is assumed to follow any string. In a defining expression, the right end matches the ending of any source string, and its value is the empty string "".

RuleCall.

A name of a translation rule followed by a translation sequence enclosed in parentheses.

RuleCall  ::=  RuleName "(" TranSequence ")"

When a rule is called, the value of the translation sequence is parsed by the defining expression of the rule. Then the value of the target sequence of the rule is returned as the value of the rule call. A failure of a rule call during parsing causes the current option to fail. If all parsing options fail or the target sequence of the rule fails, then the rule call fails.

Target.

A translation sequence that follows the translation marker "=>" of a translation rule. When the translation rule is called, the value of the target sequence is the value returned by the rule call.

Test.

A test consists of an equal sign "=" or an nonequal sign "!=" followed by a generation term or a translation sequence enclosed in parentheses.

Test  ::=  ("=" | "!=") (GenerationTerm | "(" TranSequence ")")

If the preceding string matches the value that follows, the equal test is true and the nonequal test is false. Otherwise, the nonequal test is true and the equal test is false.

TranTerm.

A translation term (TranTerm) has the same options as a term in an EBNF rule with the addition of an optional variable assignment and an optional test.

TranTerm  ::=  (CategorySymbol | Literal | "(" DefiningExpression ")" )
     ("*" | "+" | "?")? VarAssignment? Test?

If a test occurs at the end of any term, a copy of the string matched by the term is tested. If the test is true, the parser continues; otherwise, it backtracks to another option in the defining expression.

TranSequence.

A sequence of one or more generation terms separated by white space.

TranSequence  ::=  GenerationTerm (WhiteSpace GenerationTerm)*

The value of the translation sequence is the concatenation of the values of all the generation terms in the order in which they occur.

VarAssignment.

A variable assignment consists of a period "." followed by an identifier called a variable.

VarAssignment  ::=  "." Variable

The string of the source language matched by the immediately preceding term is assigned as the value of the variable. Any value previously assigned to the variable must be saved in case a subsequent mismatch in the parsing of the source string causes the parser to backtrack and try another option. A variable that has never been assigned a value has the empty string "" as its default value.

As an example, the following translation rule named Paragraph matches any text string and replaces all blank lines by the HTML paragraph tag "<p>".

Paragraph  ::=  LeftEnd String.Front
                ("\n" WhiteSpace? "\n" String.Back)? RightEnd
           =>   Front (""=Back ? "" : "\n<p>" Paragraph(Back))

After the parser finishes matching the defining expression to the source string, the target sequence is evaluated to generate the value of the rule call. In this case, it generates the value of Front concatenated to the value of the conditional. If Back is the empty string, the conditional returns the empty string. Otherwise, it returns the value "\n<p>" concatenated to the result of calling Paragraph to continue processing Back.

Annex C (Informative) Bibliography

1. Chein, Michel, ed. (1996) Revue d'Intelligence artificielle, Special Issue on Conceptual Graphs, vol. 10, no. 1.
2. Eklund, Peter W., Gerard Ellis, & Graham Mann, eds. (1996) Conceptual Structures: Knowledge Representation as Interlingua, Lecture Notes in AI 1115, Springer-Verlag, Berlin.
3. Ellis, Gerard, Robert A. Levinson, William Rich, & John F. Sowa, eds. (1995) Conceptual Structures: Applications, Implementation, and Theory, Lecture Notes in AI 954, Springer-Verlag, Berlin.
4. Ganter, Bernhard, & Guy W. Mineau, eds. (2000) Conceptual Structures: Logical, Linguistic, and Computational Issues, Lecture Notes in AI 1867, Springer-Verlag, Berlin.
5. Hansen, Hans Robert, Robert M?hlbacher, & Gustaf Neumann (1992) Begriffsbasierte Integration von Systemanalysemethoden, Physica-Verlag, Heidelberg. Distributed by Springer-Verlag.
6. Lukose, Dickson, Harry Delugach, Mary Keeler, Leroy Searle, & John Sowa, eds. (1997) Conceptual Structures: Fulfilling Peirce's Dream, Lecture Notes in AI 1257, Springer-Verlag, Berlin.
7. Nagle, T. E., J. A. Nagle, L. L. Gerholz, & P. W. Eklund, eds. (1992) Conceptual Structures: Current Research and Practice, Ellis Horwood, New York.
8. Nogier, Jean-Fran?ois (1991) G?n?ration automatique de langage et graphes conceptuels, Herm?s, Paris.
9. Mineau, Guy W., Bernard Moulin, & John F. Sowa, eds. (1993) Conceptual Graphs for Knowledge Representation, Lecture Notes in AI 699, Springer-Verlag, Berlin.
10. Mugnier, Marie-Laure, & Michel Chein, eds. (1998) Conceptual Structures: Theory, Tools, and Applications, Lecture Notes in AI 1453, Springer-Verlag, Berlin.
11. Perez, Sandra K., & Anthony K. Sarris, eds. (1995) Technical Report for IRDS Conceptual Schema, Part 1: Conceptual Schema for IRDS, Part 2: Modeling Language Analysis, X3/TR-14:1995, American National Standards Institute, New York, NY.
12. Pfeiffer, Heather D., & Timothy E. Nagle, eds. (1993) Conceptual Structures: Theory and Implementation, Lecture Notes in AI 754, Springer-Verlag, Berlin.
13. Rassinoux, Anne-Marie (1994) Extraction et Repr?sentation de la Connaissance tir?e de Textes M?dicaux, ?ditions Syst?mes et Information, Geneva.
14. Schr?der, Martin (1994) Erwartungsgest?tzte Analyse medizinischer Befundungstexte: Ein wissensbasiertes Modell zur Sprachverarbeitung, Infix-Verlag, Sankt Augustin.
15. Sowa, John F. (1976) "Conceptual graphs for a database interface," IBM Journal of Research and Development, vol. 20, no. 4, pp. 336-357.
16. Sowa, John F. (1984) Conceptual Structures: Information Processing in Mind and Machine, Addison-Wesley, Reading, MA.
17. Sowa, John F., ed. (1992) Knowledge-Based Systems, Special Issue on Conceptual Graphs, vol. 5, no. 3, September 1992.
18. Sowa, John F. (2000) Knowledge Representation: Logical, Philosophical, and Computational Foundations, Brooks Cole Publishing Co., Pacific Grove, CA.
19. Stumme, Gerd, ed. (2000) Working with Conceptual Structures: Contributions to ICCS'2000, Shaker-Verlag, Aachen.
20. Tepfenhart, William, and Walling Cyre, eds. (1999) Conceptual Structures: Standards and Practices, Lecture Notes in AI 1640, Springer-Verlag, Berlin.
21. Tepfenhart, William M., Judith P. Dick, and John F. Sowa, eds. (1994) Conceptual Structures: Current Practice, Lecture Notes in AI 835, Springer-Verlag, Berlin.
22. Way, Eileen C. (1991) Knowledge Representation and Metaphor, Kluwer Academic Publishers, Dordrecht.
23. Way, Eileen C., ed. (1992) Journal of Experimental and Theoretical Artificial Intelligence (JETAI), Special Issue on Conceptual Graphs, vol. 4, no. 2.

   Last Modified: