Old Version
Of Conceptual Graph Standard

11 August 1999

This web page has been superseded by the updated version of the conceptual graph standard.


Table of Contents

Foreword

1 Scope

2 Conformance

3 Normative References

4 Terms and Definitions

5 CG Representations

  • 5.1 Interrelationships
  • 5.2 Example
  • 6 Abstract Syntax

  • 6.1 Conceptual Graph
  • 6.2 Concept
  • 6.3 Conceptual Relation
  • 6.4 Lambda Expression
  • 6.5 Concept Type
  • 6.6 Relation Type
  • 6.7 Referent
  • 6.8 Context
  • 6.9 Coreference Set
  • 6.10 Knowledge Base
  • 7 Conceptual Graph Interchange Form (CGIF)

  • 7.1 Lexical Categories
  • 7.2 Syntactic Categories
  • 7.3 Mapping AS to CGIF
  • 8 Extended Syntax

  • 8.1 Special Contexts
  • 8.2 Defined Quantifiers
  • 9 Logical Foundations

  • 9.1 Translation to Predicate Calculus
  • 9.2 Canonical Formation Rules
  • 9.3 Rules of Inference
  • 9.4 Conformance Levels
  • Annex A (Informative) Presentation Formats

  • A.1 Display Form
  • A.2 Linear Form (LF)
  • Annex B (Normative) Metalevel Conventions

  • B.1 Extended BNF Rules
  • B.2 Translation Rules
  • Annex C (Informative) Bibliography


    Foreword

    This draft proposed American National Standard (dpANS) was developed by the NCITS.T2 Committee on Information Interchange and Interpretation. During that development, the following persons, who were members of NCITS.T2, commented on and/or contributed to this dpANS:

    In addition to the NCITS.T2 committee members, the following users and implementers of conceptual graph systems commented on early drafts of this dpANS, tested its implementability in whole or in part, and/or suggested revisions or extensions to the specifications:


    1 Scope

    This dpANS specifies the syntax and semantics of conceptual graphs (CGs) and their representation as machine-readable character strings in the conceptual graph interchange form (CGIF). CGs have been developed as a conceptual schema language, as specified by ISO/IEC 14481 on Conceptual Schema Modeling Facilities (CSMF). CGIF has been designed for interchange between CSMF systems or between other IT systems that require a structured representation for logic. This Standard 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

    An IT system is in conformance with this dpANS if it can accept information expressed in the conceptual graph interchange form (CGIF) defined in Chapter 7, translate that information to some internal representation, and then translate its internal representation to CGIF in a form that is equivalent to the original input according to the criteria defined in Chapter 9. The level of conformance of the IT system shall be specified by a conformance pair, which consists of two identifiers called the style and the expressiveness:

    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.

    Chapter 9 specifies the identifiers that shall be used to represent the style and expressiveness of a conformance pair.


    3 Normative References

    The following normative documents contain provisions, which, through reference in this text, constitute provisions of this dpANS. For dated references, subsequent amendments to, or revisions of, any of these publications do not apply. However, parties to agreements based on this dpANS are encouraged to investigate the possibility of applying the most recent editions of the normative documents indicated below. Members of ISO and IEC maintain registers of currently valid International Standards. ANSI maintains a register of currently valid American National Standards.

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

    ISO/IEC 14481:1998, Information Technology (IT) - Conceptual Schema Modeling Facilities (CSMF).

    ANSI X3.42:1990, Information Technology (IT) - Representation of numerical values in character strings for information interchange.


    4 Terms and Definitions

    For the purpose of this dpANS, the terms and definitions given in ISO/IEC 10646-1, ISO/IEC 14481, ANSI X3.42, and the following list apply. Some terms may be shortened to acronyms or abbreviations, which are listed in parentheses after the term. The term "abstract syntax", for example, may be abbreviated "AS", and "conceptual relation" may be abbreviated "relation".

    abstract syntax (AS).
    A notation-independent specification of all semantically significant features of conceptual graphs.

    actor.
    A conceptual relation whose semantics may be computed or otherwise determined by an IT system external to the current knowledge base. It may affect or be affected by external entities that are not represented in the abstract syntax.

    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 knowledge base. 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.

    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 not significant: two identifiers that differ only in the case of one or more letters are considered identical.

    indexical.
    A designator represented by the character "#" followed by an optional identifier. It is used by implementation-dependent methods for locating the referent of a concept.

    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 knowledge base. Individual markers cannot be used to identify individuals across different knowledge bases, but within any single knowledge base, they can serve as unique identifiers or surrogates for the entities referenced in that knowledge base.

    knowledge base (KB).
    A context with four nested contexts: a type hierarchy, a relation 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 knowledge base.

    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.

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

    relation type label (relation label).
    An identifier that specifies a type of conceptual relation.

    scoping context.
    A special context with the type label SC, which is used to delimit the scope of quantifiers. No conceptual relation may be linked to any context of type SC.

    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 If, Then, Either, Or, and SC.

    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.

    valence.
    A nonnegative integer that specifies the number of arcs that link a conceptual relation to concepts. All conceptual relations with the same relation 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 Interrelationships

    A conceptual graph (CG) is a representation for logic specified by the abstract syntax (AS) defined in Chapter 6 of this dpANS. Informally, a CG is a structure of concepts and conceptual relations where every arc links a concept node and a conceptual relation node. Formally, the abstract syntax specifies the CG structures and constraints without commitments to any concrete notation or implementation. Chapter 6 presents the abstract specifications of conceptual graphs in ten normative sections; each section concludes with an informative note that illustrates and explains the abstract details. CGs may be implemented in any machine-readable representation or any humanly readable style that preserves the information specified by the abstract syntax.

    For communication between machines, Chapter 7 specifies a concrete syntax called the conceptual graph interchange form (CGIF), which has a simplified syntax and a restricted character set designed for compact storage and efficient parsing. Chapter 8 specifies syntactic extensions, which can be translated to the basic CGIF form that maps to the abstract syntax. For communication with human users, two concrete notations have become traditional: 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 Appendix A. Chapter 9 defines the semantics of conceptual graphs by a normative translation to predicate calculus.


    5.2 Example

    To illustrate the abstract syntax and concrete notations presented in this dpANS, Figure 1 shows the display form of a conceptual graph that represents the propositional content of the English sentence John is going to Boston by bus.

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

    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:

    This English reading is a convenience that has no normative status. The numbering or direction of the arcs takes precedence over any such mnemonics.

    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].
    
    
    In this form, the concepts are represented by square brackets instead of boxes, and the conceptual relations are represented by parentheses instead of circles. A hyphen at the end of a line indicates that the relations attached to the concept are continued on subsequent lines.

    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])
    
    
    CGIF is intended for transfer between IT systems that use CGs as their internal representation. For communication with systems that use other internal representations, CGIF can be translated to the Knowledge Interchange Format (KIF):
    
    (exists ((?x Go) (?y Person) (?z City) (?w Bus))
    
            (and (Name ?y John) (Name ?z Boston)
    
                 (Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?w)))
    
    
    Although DF, LF, CGIF, and KIF look very different, their semantics is defined by the same logical foundations. Any semantic information expressed in any one of them can be translated to the others without loss or distortion. Formatting and stylistic information, however, may be lost in translations between DF, LF, CGIF, and KIF.


    6 Abstract Syntax


    6.1 Conceptual Graph

    A conceptual graph g is a bipartite graph that has two kinds of nodes called concepts and conceptual relations.

    Comment.

    To illustrate this definition, consider the conceptual graph in Figure 1 for the sentence John is going to Boston by bus. The term bipartite means that every arc of a CG links a conceptual relation to a concept; there are no arcs that link concepts to concepts or relations to relations. Two of the six arcs in the CG belong to (Agnt), two belong to (Dest), and the remaining two belong to (Inst).

    A 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 linear form (LF):

    
    [Person: John]¬(Agnt)¬[Go]
    
    [Go]®(Dest)®[City: Boston]
    
    [Go]®(Inst)®[bus].
    
    
    These three star graphs constitute a disconnected CG, which does not indicate whether the three copies of [Go] refer to the same instance or different instances of going. If they refer to the same instance, the three identical concepts of type [Go] could be overlaid or joined to form the connected CG in Figure 1.


    6.2 Concept

    Every concept has a concept type t and a referent r.

    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

    Every conceptual relation r has a relation type t and a nonnegative integer n called its valence.

    Certain conceptual relations, called actors, may have side effects that are not represented in the abstract syntax; formally, however, actors are treated like other conceptual relations.

    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

    A person is between a rock and a hard place.

    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 towards 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].
    
    
    The hyphen after the relation indicates that its other arcs are continued on subsequent lines. The two arcs that point towards the relation are numbered 1 and 2. The arc that points away is the last or third arc; the number 3 may be omitted, since it is implied by the outward pointing arrow. For monadic relations, both the number 1 and the arrow pointing towards the circle are optional. For dyadic relations, the arcs are either numbered 1 and 2, or the first arc points towards the circle and the second arc points away.


    6.4 Lambda Expression

    For any nonnegative integer n, an n-adic lambda expression e is a conceptual graph, called the body of e, in which n concepts have been designated as formal parameters of e.

    Comment.

    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 l. If n is greater than 1, the parameters may be marked l1, l2, ..., ln. 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 l1 and the name Boston with l2:

    
    [Person: l1]¬(Agnt)¬[Go]®(Dest)®[City: l2].
    
    
    Since this is a dyadic lambda expression, its signature is a pair of types <Person,City>, which come from the type fields of the formal parameters. This lambda expression may be used to define a conceptual relation that relates a person to a city.

    To simplify the parsing, the CGIF notation avoids the character l 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))
    
    
    For every n-adic lambda expression, the keyword lambda is following by a list of n pairs that specify the formal parameters. Each pair consists of a type, such as Person, and a defining label, such as *x. The list of n types is the signature of the lambda expression.


    6.5 Concept Type

    A type hierarchy is a partially ordered set T whose elements are called type labels. Each type label in T is specified as primitive or defined.

    Comment.

    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: l]®(Loc)®[State: Maine].
    
    
    The character "l" indicates that the concept [Farmer] is the formal parameter, and the sequence (Farmer) is the signature of the lambda expression. The type label of the formal parameter is always a supertype of the newly defined type: Farmer ³ MaineFarmer. As an alternate notation, type labels can be defined with the keyword type and a variable:
    
    type MaineFarmer(*x) is [Farmer: ?x]®(Loc)®[State: Maine].
    
    
    Either the type label MaineFarmer or its defining lambda expression could be placed in the type field of a concept. The following two conceptual graphs are equivalent ways of saying Every Maine farmer is laconic:
    
    [MaineFarmer: "]®(Attr)®[Laconic].
    
    

    [ [Farmer: l]®(Loc)®[State: Maine]: "]®(Attr)®[Laconic].

    The second graph may be read Every farmer who is located in the state of Maine is laconic. Either graph could be converted to the other by interchanging the type label and its defining lambda expression.


    6.6 Relation Type

    A relation hierarchy is a partially ordered set R whose elements are called relation labels. Each relation label is specified as primitive or defined, but not both.

    Comment.

    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: l1]¬(Agnt)¬[Go]®(Dest)®[City: l2] ].
    
    
    This definition says that the relation GoingTo is defined by a lambda expression that relates a person (marked by l1), who is the agent (Agnt) of the concept [Go], to a city (marked by l2), which is the destination (Dest) of [Go]. With this relation, the graph for the sentence John is going to Boston could be represented by the following CG:
    
    [Person: John]®(GoingTo)®[City: Boston].
    
    
    This graph can be expanded to a more detailed graph by replacing the relation type label GoingTo with its definition:
    
    [Person: John]®([Person: l1]¬(Agnt)¬[Go]-
    
         ®(Dest)®[City: l2])®[City: Boston].
    
    
    The next step is to remove the lambda expression from inside the circle or parentheses, to join the first parameter [Person: l1] with the concept attached to the first arc, and to join the second parameter [City: l2] with the concept attached to the second arc:
    
    [Person: John]¬(Agnt)¬[Go]®(Dest)®[City: Boston].
    
    
    This graph says that the person John is the agent of going and that the city Boston is the destination of going. Each step of this derivation could be reversed to derive the original graph from the expanded graph.


    6.7 Referent

    The referent of a concept is specified by a quantifier, a designator, and a descriptor.

    Comment.

    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 this dpANS; and a name is a symbol that determines the referent by some conventions that are independent of the current knowledge base. A descriptor is a CG that describes some aspect of the referent. Following are some examples:

    In each of the above concepts, there is an implicit existential; the concept [String: "abcdefg"], for example, may be read There exists a string, whose form is represented by the literal "abcdefg". Two or more designators in the same concept represent different ways of indicating the same referent, as in the concept [Cat: Yojo #5549], which says that the cat named Yojo is cataloged as individual #5549.

    The defined quantifiers include the universal quantifier, which is represented by the character """ 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

    A plumber is carrying a pipe.

    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 this dpANS.


    6.8 Context

    A context C is a concept whose designator is a nonblank conceptual graph g.

    Comment.

    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

    Tom believes that Mary wants to marry a sailor.

    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 [T]) marries a sailor. The dotted line, called a coreference link, shows that the concept [T] 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] ]].
    
    
    Both the display form and the linear form follow the same rules for the scope of quantifiers. The part of the graph outside the nested contexts contains three concepts: [Person: Tom], [Believe], and the proposition that Tom believes. That part of the graph asserts information that is assumed to be true of the real world. Inside the proposition box are three more concepts: [Person: Mary], [Want], and the situation that Mary wants. Since those three are only asserted within the context of Tom's belief, the graph does not imply that they must exist in the real world. Since Mary is a named individual, one might give her the benefit of the doubt and assume that she also exists; but her desire and the situation she supposedly desires exist in the context of Tom's belief. If his belief is false, the referents of those concepts might not exist in the real world. Inside the context of the desired situation are the concepts [Marry] and [Sailor], whose referents exist within the scope of Mary's desire, which itself exists only within the scope of Tom's belief.


    6.9 Coreference Set

    A coreference set C in a conceptual graph g is a set of one or more concepts selected from g or from graphs nested in contexts of g.

    Comment.

    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 [T] is an example of a coreference link. The concept [T] 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 [T].

    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 Knowledge Base

    A knowledge base is a context of type KnowledgeBase whose designator is a conceptual graph consisting of four concepts:

    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 knowledge base. 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 contents of the knowledge base must satisfy the following constraints:

    The type labels KnowledgeBase, TypeHierarchy, RelationHierarchy, CatalogOfIndividuals, and Assertion are metalevel labels that need not be specified in T. However, if a knowledge base contains information about a knowledge base, including knowledge bases that may be nested inside itself, then its type hierarchy must specify the metalevel labels.

    Comment.

    The outermost context of a knowledge base 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"] ]]
    
    
    Four concepts in the nested CG have individual markers: #5539 marks a cat named Yojo; #3714 marks a village named Croton-on-Hudson; #7603 marks a dog named Macula; and #2092 marks a state named New Hampshire. The other concepts and relations specify additional information about the four cataloged individuals. The outermost context of the same knowledge base may make further assertions about them, but the problem of finding the individuals themselves is outside the scope of the formalism.

    Individuals that are not cataloged might be implied by existential quantifiers in some concepts of a knowledge base. 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 knowledge base, 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 knowledge bases. Most such systems can be represented as special cases of a CG knowledge base:


    7 Conceptual Graph Interchange Form (CGIF)

    The conceptual graph interchange form (CGIF) is a representation for conceptual graphs intended for transmitting CGs across networks and between IT systems that use different internal representations. All features defined by the abstract syntax of Chapter 6 and the extensions of Chapter 8 are representable in CGIF. The CGIF syntax ensures that all necessary syntactic and semantic information about a symbol is available before the symbol is used; therefore, all translations can be performed during a single pass through the input stream. The CGIF syntax is specifed in terms of the Extended BNF (EBNF) rules and metalevel conventions, which are defined in Annex B.


    7.1 Lexical Categories

    The lexical categories of CGIF are defined as sequences of characters as specified in ISO/IEC 10646-1. Characters outside the 7-bit subset of ISO/IEC 10646-1 occur only in strings that represent identifiers, literals, and comments. By using escape sequences in such strings, it is possible to encode and transmit CGIF in the 7-bit subset of ISO/IEC 10646-1. Numerical values are represented by the conventions of ANSI X3.42. The following lexical categories may be used in EBNF rules in this chapter or in the translation rules in chapters 8 and 9:

    EscapeSequence.
    An escape sequence is a sequence of characters beginning with a backslash that is used to represent certain characters. Nine escape sequences are said to be valid:

    1. Backspace: "\b".

    2. Horizontal tab: "\t".

    3. Linefeed: "\n".

    4. Form feed: "\f".

    5. Carriage return: "\r".

    6. Double quote: "\"".

    7. Single quote: "\'".

    8. Backslash: "\\".

    9. Unicode: "\uXXXX", where each X represents one of the following hexadecimal digits: "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "a", "b", "c", "d", "e", "f", "A", "B", "C", "D", "E", "F".

    In CGIF, escape sequences appear only in identifiers, comments, and quoted strings. In identifiers, none of the first eight escape sequences may appear; only Unicode escapes that represent a letter or digit that is outside the 7-bit subset of ISO/IEC 10646-1 may appear in an identifer. In comments and quoted strings, Unicode escapes may be used to represent any character, including those in the 7-bit and 8-bit subsets of ISO/IEC 10646-1.

    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 | "_")*
    
    
    Case is not significant: two identifiers that differ only in the case of one or more letters are said to match. As an example, the identifier "CarStop" matches "CarsTop" and "carstop".

    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.

    Number.
    A number is a sequence of characters that represents an integer or a floating-point number as defined in ANSI X3.42.

    String.
    A string is a sequence of zero or more characters as specified in ISO/IEC 10646-1. The first eight escape sequences must be used to represent the characters they define; a Unicode escape sequence must be used for all characters outside the 8-bit subset of ISO/IEC 10646-1. Characters in the 8-bit subset may be represented by a Unicode escape sequence. The backslash "\\", double quote "\"", or single quote "\'" or their Unicode representations "\u005c", "\u0022", and "\u0027" may only occur in valid escape sequences.

    WhiteSpace.
    White space is a sequence of one or more characters that represent a space, a horizontal tab, a carriage return, a line feed, or a form feed.

    Comment.

    These definitions allow CG tools that use 7 or 8 bits to represent each character to maintain compatibility with tools that use 16 or more bits per character. Tools with the smaller character sets may leave the Unicode escapes unprocessed in identifiers and quoted strings, while tools that support the larger character sets may expand them to their 16-bit forms.


    7.2 Syntactic Categories

    Every syntactic category of CGIF is first described in English and then defined formally by an EBNF rule, as defined in Annex B. Each EBNF rule is followed by an English statement of possible constraints and implications. Context-sensitive constraints, which are determined by the abstract syntax defined in Chapter 6 or by the extended syntax defined in Chapter 8, are stated with a reference to the governing section in Chapter 6 or 8. In all questions of interpretation, the EBNF rules take precedence over the English descriptions and statements. The following syntactic categories may be used in EBNF rules and translation rules:

    Actor.
    An actor begins with a less-than symbol "<" followed by a relation type label or a lambda expression. It continues with zero or more arcs, a vertical bar "|", zero or more arcs, and an optional semicolon ";" and actor comment. It ends with a greater-than symbol ">".
    
    Actor  ::=  "<" (RelTypeLabel | LambdaExpression)
    
         Arc* "|" Arc* (";" ActorComment)? ">"
    
    
    The arcs that precede the vertical bar are called input arcs, and the arcs that follow the vertical bar are called output arcs. If the relation type label or lambda expression has valence n, the total number of input and output arcs must be equal to n.

    ActorComment.
    An actor comment is a sequence of zero or more characters that appears in a actor after a semicolon ";" and before the final ">". Any occurrence of ">" terminates an actor comment; the corresponding Unicode escape \u003e does not terminate an actor comment.

    Arc.
    An arc of a conceptual relation is specified by either a concept or a bound label.
    
    Arc  ::=  Concept | BoundLabel
    
    
    Formally, an arc is a pair consisting of one concept and one conceptual relation. In CGIF, the concept attached to the arc is determined by the concept or bound label in its specification; the relation to which the arc belongs is the one in whose specification the arc is contained.

    BoundLabel.
    A bound label (BoundLabel) consists of a question mark "?" followed by an identifier.
    
    BoundLabel  ::=  "?" Identifier
    
    
    A bound label is said to match a defining label if their identifiers are identical, ignoring possible differences between uppercase and lowercase letters.

    CG.
    A conceptual graph (CG) is a list of zero or more concepts, conceptual relations, actors, special contexts, or CG comments.
    
    CG  ::=  (Concept | Relation | Actor | SpecialContext | CGComment)*
    
    
    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.

    CGComment.
    A CG comment is a sequence of zero or more characters enclosed in the strings "/*" and "*/".
    
    CGComment  ::=  "/*" Character* "*/"
    
    
    Any occurrence of "*/" terminates a CG comment; the corresponding Unicode escape "\u002a\u002f" does not terminate a CG comment.

    Concept.
    A concept begins with a left bracket "[" followed by an optional type followed by either optional coreference links or a colon and optional coreference links and optional referent in any order. Then comes an optional semicolon ";" followed by a concept comment. Finally, the concept is terminated by a right bracket "]".
    
    Concept  ::=  "[" Type? (Coreflinks? | (":" {Coreflinks?, Referent?}))
    
                            (";" ConComment)? "]"
    
    
    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 [T] could be written [?x], and its implict type would be Entity.

    ConComment.
    A concept comment (ConComment) is a sequence of zero or more characters that appears in a concept after a semicolon ";" and before the final "]". Any occurrence of "]" terminates a concept comment; the corresponding Unicode escape "\u005d" does not terminate a concept comment.

    ConTypeLabel.
    A concept type label (ConTypeLabel) is any identifier other than the five special context labels "If", "Then", "Either", "Or", and "SC" or the reserved label "Else".

    CorefLinks.
    Coreference links (CorefLinks) 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 (DefLabel) consists of 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 knowledge base 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. /p>

    Descriptor.
    A descriptor is a conceptual graph that is nested in the referent field of a concept.
    
    Descriptor  ::=  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. Any CG may be used as a descriptor, including a blank CG.

    Designator.
    A designator is a literal, a locator, or an empty string that represents an undefined designator.
    
    Designator  ::=  Literal | Locator | ""
    
    

    Descriptor.
    A descriptor is a string, possibly empty, that represents a CG in the referent of some concept.

    EncodedLiteral
    An encoded literal is the character "%" followed by an identifier and a string enclosed in double quotes.
    
    EncodedLiteral  ::=  "%" Identifier "\"" String "\""
    
    
    The identifier specifies some implementation-dependent method for interpreting the following string.

    FormalParameter.
    A formal parameter consists of a type and a optional defining label.
    
    FormalParameter  ::=  Type [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  ::=  "#" Integer
    
    
    The integer specifies an index to some entry in a catalog of individuals.

    LambdaExpression.
    A lambda expression begins with "(" and the keyword "lambda", it continues a signature and a conceptual graph, and it ends with ")".
    
    LambdaExpression  ::=  "(" "lambda" Signature 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, a string enclosed in double quotes, or an encoded literal.
    
    Literal  ::=  Number | "\"" String "\"" | EncodedLiteral
    
    
    Any double quote that occurs in a literal must be preceded with a backslash.

    Locator.
    A locator is a name, an individual marker, or an indexical.
    
    Locator  ::=  Name | IndividualMarker | Indexical
    
    

    Name.
    A name is a string of one or more letters or a string of one or more arbitrary characters enclosed in single quotes "\'".
    
    Name  ::=  Letter+ | ("\'" Character+ "\'")
    
    
    The quotes are optional for one-word names like John, but they are required for names that contain nonletters, such as 'John Q. Public'. A string in double quotes, such as "John Q. Public", is a literal.

    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 features are required, the negation can be expressed by the unabbreviated form with an explicit Neg relation.

    In CGIF, the tilde "~" is the only symbol used to abbreviate Neg. In LF or DF, the not sign "¬" may be used as an alternative to "~", but "¬" is avoided in CGIF because it is outside the 7-bit subset of ISO/IEC 10646-1.

    Quantifier.
    A quantifier is an existential or a defined quantifier.
    
    Quantifier  ::=  Existential | DefinedQuantifier
    
    
    An existential quantifier is represented by an empty string "". A defined quantifier is defined in Chapter 8 by an expansion of the containing CG to an equivalent CG that does not contain that quantifier.

    Referent.
    A referent consists of a quantifier, a designator, and a descriptor in any order.
    
    Referent  ::=  {Quantifier, Designator, Descriptor}
    
    
    Any or all of the three parts of a referent may be an empty string. An empty referent, which implies an existential quantifier, an undefined designator, and a blank CG as descriptor, indicates that the concept refers to something that conforms to the concept type, but without giving any further information that might help to identify it.

    Relation.
    A conceptual relation (Relation) begins with a left parenthesis "(" followed by a relation type label or a lambda expression. It continues with zero or more arcs and an optional semicolon ";" and relation comment. It ends with a right parenthesis ")".
    
    Relation  ::=  "(" (RelTypeLabel | LambdaExpression)
    
         Arc* (";" Comment)? ")"
    
    
    If the relation type label or the lambda expression has a valence n, the relation must have a sequence of exactly n arcs.

    RelComment.
    A relation comment is a sequence of zero or more characters that appears in a conceptual relation after a semicolon ";" and before the final ")". Any occurrence of ")" terminates a relation comment; the corresponding Unicode escape "\u0029" does not terminate a relation comment.

    RelTypeLabel.
    A relation type label (RelTypeLabel) is any identifier other than "lambda".

    Signature.
    A signature is a parenthesized list of zero or more formal parameters separated by commas.
    
    Signature  ::=  "(" (FormalParameter ("," FormalParameter)*)? ")"
    
    

    SpecialConLabel.
    A special context label (SpecialConLabel) is one of the five identifiers "If", "Then", "Either", "Or", and "SC".
    
    SpecialConLabel  ::=  "If" | "Then" | "Either" | "Or" | "SC"
    
    
    The identifier "Else" is reserved for possible future use as a special context label. None of the special context labels or the identifier "Else" may be used as a type label.

    SpecialContext.
    A special context is a negation or a left bracket, a special context label, a CG, and a right bracket.
    
    SpecialContext  ::=  Negation | "[" SpecialConLabel CG "]"
    
    
    In Chapter 8, every special context is a defined by a translation to a context as defined in Section 6.8. Therefore, it is a kind of concept. But unlike other concepts, a special context may not have a defined quantifier, coreference labels, or attached conceptual relations.

    Type.
    A type is a concept type label or a monadic lambda expression.
    
    Type  ::=  ConTypeLabel
    
            |  "(lambda" "(" FormalParameter ")" CG ")"
    
    

    Comment.

    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])
    
    
    For more compact storage and transmission, all white space not contained in comments or enclosed in quotes may be eliminated:
    
    (Betw[Rock][Place*x1][Person])(Attr?x1[Hard])
    
    
    This translation takes the option of nesting all concept nodes inside the conceptual relation nodes. A logically equivalent translation, which uses more coreference labels, moves the concepts outside the relations:
    
    [Rock *x1] [Place *x2] [Person *x3] (Betw ?x1 ?x2 ?x3)
    
    [Hard ?x4] (Attr ?x2 ?x4)
    
    
    The concept and relation nodes may be listed in any order provided that every bound label follows the defining node for that label.

    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. ])
    
    
    This example shows how literals of any kind may be represented in the referent field of a concept. The identifiers "WAV" and "JPEG" specify the method of encoding. In DF, the sound might be represented by a transcription such as "Clink Clankety Scrape" or it could be converted to audio when someone clicks a mouse on the concept node. To avoid storing multiple copies of large literals, such as sound or video, a single copy might be stored outside the CG system with only a locator in the referent field.

    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]) ]) ])
    
    
    Note that the concept [T] in Figure 4, which may be represented [?x3] in LF or CGIF, may also be omitted completely in CGIF since the coreference label ?x3 inside the conceptual relation of type Agnt is sufficient to show the connection. As these examples illustrate, CGIF is not as readable as DF, but it contains the equivalent semantic information. To reconstruct an exact image of the original DF, the comment fields in the concept and relation nodes may contain additional layout information to specify the style and placement of the nodes.


    7.3 Mapping AS to CGIF

    Whenever a feature of the abstract syntax (AS) specified in Chapter 6 has the same name as some CGIF category of Section 7.2, the AS feature is represented by a string defined by that CGIF category. The mapping of AS features to CGIF categories is not one to one because of the following exceptions:

    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.

    Each subsection from 7.3.1 to 7.3.10 specifies the CGIF strings that represent the AS features defined in the section from 6.1 to 6.10 respectively.

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

    7.3.2 Concept.
    Every concept c is 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.

    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.

    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:

    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:

    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.

    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.

    7.3.10 Knowledge Base.
    A knowledge base KB is represented by a context of type KowledgeBase, which contains a set of four contexts whose types are TypeHierarchy, RelationHierarchy, CatalogOfIndividuals, and Assertion. Its syntax is defined by the following translation rule (see Annex B.2):
    
    KB  ::=  "[" "KnowledgeBase" ":"
    
               { "[" "TypeHierarchy" ":" CG.T "]",
    
                 "[" "RelationHierarchy" ":" CG.R "]",
    
                 "[" "CatalogOfIndividuals" ":" CG.C "]",
    
                 "[" "Assertion" ":" CG.O "]" } "]"
    
    
    When the pattern part of this rule matches a CGIF string that represents a knowledge base, 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 knowledge base 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 knowledge base; it may also assert some background knowledge about those individuals. All other assertions that are known or assumed to be true in the current knowledge base are stated by the CG O.

    Since a knowledge base is also a concept, it may be linked to conceptual relations in a conceptual graph that makes a statement about the knowledge base, 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 knowledge base, which would then be a metaknowledge base about the nested knowledge base. Knowledge bases may be nested to any depth; a metaknowledge base may contain assertions about knowledge bases nested inside itself, but no knowledge base may contain references to a knowledge base in which it is nested.


    8 Extended Syntax

    The abstract definitions in Chapter 6 define the core structures of conceptual graphs, which are sufficient to represent all of first-order and higher-order logic. To represent logic more concisely, however, the extended syntax supports special contexts and defined quantifiers, which can all be translated to the core structures. The translation rules defined in Section B.2 provide a mechanism for mapping the extended syntax to CGIF, whose mapping to the abstract syntax is defined in Section 7.3.


    8.1 Special Contexts

    All Boolean operators can be represented in terms of conjunction and negation. The conjunction of two CGs is represented by including them in the same context. The negation of any CG is represented by including it in a negation. For convenience and readability, some combinations of conjunction and negation are defined as special contexts, whose syntax is defined by EBNF rules and whose semantics is defined by translation rules that convert them to the basic CGIF notation.

    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 "]" "]"
    
    
    Any CGIF string of this form can be translated to a basic CGIF string by the TrIfThen translation rule:
    
    TrIfThen  ::=  "[" "If" CG.x "[" "Then" CG.y "]" "]"
    
               =>  "~[" x "~[" y "]" "]"
    
    
    The first line of this rule matches any IfThen string; during the match, it assigns the string that represents the first CG to the variable x and the string that represents the second CG to y. Then the second line generates a string that encloses the two Concept strings x and y in nested negations.

    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 #]) ]]
    
    
    The TrIfThen rule translates this string to the following:
    
    ~[ (Has [Person 'Sam'] [Car]
    
        ~[ [Drive *x] (Agnt ?x [Person 'Sam]) (Thme ?x [Car #]) ]]
    
    
    This string is corresponds to the sentence It is false that Sam has a car, and Sam does not drive the 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 "]")* "]"
    
    
    Any CGIF string of this form can be translated to the basic CGIF form by the TrEither translation rule and the TrOrs rule:
    
    TrEither  ::=  "[" "Either" CG.x
    
                       ("[" "Or" CG "]")*.y "]"
    
               =>  "~[" x TrOrs(y) "]"
    
    
    The first line of this rule matches a context with the label "Either" and assigns the first CG, which may be blank, to the variable x. The second line matches zero or more contexts with the label "Or" and assigns all of them to the variable y. Then the third line generates a negative context containing x and the result of translating y by the TrOrs rule.
    
    TrOrs  ::=  ("[" "Or" CG.x "]")?.y String.z RightEnd
    
            =>  (y="" ? "" | "~[" x "]" TrOrs(z))
    
    
    The first line of this rule matches an optional context with the special label "Or"; during the match, it assigns the nested CG to x, the possibly nonexistent context to y, and the remainder of the input string to z. Then the second line has a conditional that tests to see whether y is empty; if so, it returns the empty string; otherwise, it returns a negation of x followed by the result of applying the TrOrs rule to the string 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]) ]]
    
    
    The TrEither and TrOrs rule translate this string to the following:
    
    ~[
    
       ~[ (Has [Person Sam] [Car]) ]
    
       ~[ [Ride *x] (Agnt ?x [Person Sam]) (Inst ?x [Bus]) ]]
    
    
    Since the Either context contains the Or contexts within its scope, it is the place to put a concept that has coreference links to all the options. As an example, consider the following sentence Either a cat is on a mat, or it is eating, or it is chasing a mouse. The concept [Cat] must be placed in a context outside all three disjunctions:
    
    [Either [Cat *x]
    
       [Or (On ?x [Mat]) ]
    
       [Or (Agnt [Eat] ?x) ]
    
       [Or [Chase *y] (Agnt ?y ?x) (Thme ?y [Mouse]) ]]
    
    
    This graph is logically equivalent to the graph that represents the sentence Every cat is on a mat, is eating, or is chasing a mouse or to the graph for the sentence If there exists a cat, then it is on a mat, it is eating, or it is chasing a mouse. In all these sentences, the cat is a hypothetical or generic cat. If the speaker has a particular cat in mind, then the concept [Cat: *x] would have to be moved outside the context of Either:
    
    [Cat *x]
    
    [Either
    
       [Or (On ?x [Mat]) ]
    
       [Or (Agnt [Eat] ?x) ]
    
       [Or [Chase *y] (Agnt ?y ?x) (Thme ?y [Mouse]) ]]
    
    
    This graph corresponds to the sentence There exists a certain cat, which is on a mat, is eating, or is chasing a mouse.


    8.2 Defined Quantifiers

    [This section is still under construction.]

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

    
    (On [Cat @every] [Mat])
    
    
    The occurrence of the symbol "@every" in the referent field of the concept [Cat @every] triggers a translation rule that generates the following basic CGIF representation:
    
    ~[ [Cat: *_5219]
    
      ~[ (On ?_5219 [Mat]) ]]
    
    
    The translation rule generates a new coreference label whenever it is invoked. In this case, it generated the defining label *_5219 with the corresponding bound label ?_5219. The nest of two negations in the translated CGIF corresponds to an implication. Therefore, it can be read If there exists a cat, then it is on a mat.

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

    The macros allow the full power of logic to be used for defining generalized quantifiers. The character "¬" in the referent field represents the universal negative quantifier, which is read as the English word no. The qualifier @>18 may be read as more than 18. In combination, they can represent the sentence No trailer truck has more than 18 wheels:

    
    [TrailerTruck: ¬]®(Part)®[Wheel: {*}@>18].
    
    
    The first step of the macro expansion produces a graph for the sentence It is false that a trailer truck has more than 18 wheels:
    
    ¬[ [TrailerTruck]®(Part)®[Wheel: {*}@>18] ].
    
    
    This graph, in combination with Figure 4.8, can be used to say that every trailer truck has at least 18 and no more than 18 wheels. The qualifier @=18 can be defined by the conjunction of both these forms to say that every trailer truck has exactly 18 wheels.

    Precedence levels for quantifiers.

    In predicate calculus, the scope of quantifiers is determined either by parentheses or by the order in which the quantifiers are written, as in the following two formulas:
    
    ("x:Woman)($y:Man)married(x,y).
    
    

    ($y:Man)("x:Woman)married(x,y).

    The first formula may be read For every woman x, there exists a man y, where x married y or more simply Every woman married some man. That formula does not guarantee that each woman found a unique man, but it leaves the possibility open. The second formula, however, could be read Some man married every woman. If there is more than one woman, the man would be a bigamist.

    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 " 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: "]¬(Agnt)¬[Marry]®(Thme)®[Man] ].
    
    

    [Man: *x] (Past)®[Situation: [Woman: "]¬(Agnt)¬[Marry]®(Thme)®[?x] ].

    The first graph may be read Every woman married some man, but the second is more contorted: There exists a man that every woman married. The PAST relation attached to the contexts shows the past tense explicitly.

    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 ":

    
    (Past)®[ [Woman: "]¬(Agnt)¬[Marry]®(Thme)®[Man: @certain] ].
    
    
    In this graph, the quantifier @certain has highest precedence, " has middle precedence, and the existential in [Marry] has lowest precedence. That means that for each woman, there is a separate instance of marrying, but the same man is the bridegroom in each instance. Following are the three precedence levels for CG quantifiers:

    When new quantifiers are defined, they are assigned to one or another of these levels. The symbol @1, for example, represents the quantifier $!, which means there exists exactly one. It has the same low precedence as the implicit existential. For complex mixtures of quantifiers, the scope can be delimited by transparent contexts (marked by context brackets [ ] with no type label).


    9 Logical Foundations


    9.1 Translation to Predicate Calculus

    When a conceptual graph is represented in CGIF, the grammar rules permit several different options, all of which are logically equivalent. As an example, consider the following CGIF representation for Figure 1, which was discussed in Chapter 5:

    
    [Go *x] (Agnt ?x [Person: John]) (Dest ?x [City: Boston]) (Inst ?x [Bus])
    
    
    As another option, the grammar permits all concept nodes to be moved to the front with all arcs represented by bound variables:
    
    [Go *x] [Person: John *y] [City: Boston *z] [Bus *w]
    
    (Agnt ?x ?y) (Dest ?x ?z) (Inst ?x ?z)
    
    
    This representation takes somewhat more space and requires more coreference labels. However, it has a more direct mapping to predicate calculus:
    
    ($x:Go)($y:Person)($z:City)($w:Bus)
    
       (Name(y,'John') Ù Name(z,'Boston') Ù
    
          Agnt(x,y) Ù Dest(x,z) Ù Inst(x,w))
    
    
    In CGIF, the names John and Boston are represented in the referent fields of concepts. In predicate calculus, the Name predicate is added to indicate that they are names. In KIF, however, the absence of a question mark indicates that they are constants, and the Name predicate may be omitted. Following is the corresponding statement in KIF:
    
    (exists ((?x Go) (?w Bus))
    
            (and (Person John) (City Boston)
    
                 (Agnt ?x John) (Dest ?x Boston) (Inst ?x ?w)))
    
    
    For a given abstract CG, all the variations of CGIF permitted by the grammar are logically equivalent, and they map to statements in predicate calculus or KIF that are logically equivalent. For output, an IT system may generate any variation of CGIF permitted by the grammar; for input, it must be able to recognize all of them.

    The translation from CGIF to predicate calculus is defined by the function φ. If u is any CG, then φ(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

    All operations on conceptual graphs are based on combinations of six canonical formation rules, each of which performs one basic graph operation. Logically, each rule has one of three possible effects: it makes a CG more specialized, it makes a CG more generalized, or it changes the shape of a CG while leaving it logically equivalent to the original. All the rules come in pairs: for each specialization rule, there is a corresponding generalization rule; and for each equivalence rule, there is another equivalence rule that transforms a CG to its original shape. These rules are fundamentally graphical: they are easier to show than to describe.

    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:

    which is true or false under exactly the same circumstances as the formula that corresponds to the bottom CG:

    By the inference rules of predicate calculus, either of these two formulas can be derived from the other.

    Figure 5. Copy and simplify rules

    Example of 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

    is implied by the more specialized formula:

    Figure 6. Restrict and unrestrict rules

    Example of restrict and unrestrict rules.

    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

    is implied by the formula for the bottom CG:

    Figure 7. Join and detach rules

    Example of join and detach rules.

    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.

    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.

    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.

    Although the six canonical formation rules have been explicitly stated in terms of conceptual graphs, equivalent operations can be performed on any notation for logic.

    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.

    Let u be a conceptual graph in which some concept is a context whose designator is a nested conceptual graph v. The following canonical formation rules convert u to another CG w by operating on the nested graph v, while leaving everything else in u unchanged.

    1. Equivalence rules.

    2. Specialization rules.

    3. Generalization rules.

    In summary, negation reverses the effect of generalization and specialization, but it has no effect on the equivalence rules.


    9.3 Rules of Inference

    The canonical formation rules are the foundation for all logical operations on CGs. For each rule, there is a corresponding inference rule for predicate calculus. If some rule transforms a CG u to a CG v where u implies v, then the corresponding formula φ(u) in predicate calculus implies the formula φ(v). The graph rules, however, are usually simpler than the corresponding rules in predicate calculus.

    By handling the syntactic details of conceptual graphs, the generalization and specialization rules enable the rules of inference to be stated in a general form that is independent of the graph notation.

    Coreference links.

    Lambda conversions.

    Both Peirce and Frege recognized the need to define new relations as abstractions from other logical expressions. But with the lambda calculus, Alonzo Church (1941) was the first to formalize the rules for operating on those abstractions. Definitions 7.1.5 and 7.1.6 authorize the fundamental equivalence rule for a lambda calculus of CGs: the label for a defined concept or relation type is interchangeable with its defining lambda expression. By itself, however, this rule is not sufficient; additional conversion rules are necessary to transform the CG in which the lambda expression occurs. The two rules of lambda expansion remove the defining graph from the type field of a concept or relation node and join its formal parameters to other concepts in the current context:

    The corresponding rules of lambda contraction are the inverses of the rules of lambda expansion: if any conceptual graph g could have been derived by lambda expansion from a CG u, then g may be contracted to form u. These rules are the graph equivalents of Church's rules for lambda calculus. Like Church's version, they can be used as equivalence rules in proofs.


    9.4 Conformance Levels


    Annex A (Informative) Presentation Formats

    The abstract syntax (AS) is independent of any notation. It allows a concept to be identified with a block of computer storage or with multimedia presentations that use colors, three dimensions, specialized shapes, sound, and motion. The display form (DF) is intended as a readable two-dimensional representation that can be drawn on paper or computer screens. The linear form (LF) is convenient for keyboard entry of CGs or for printing CGs in a more compact form than DF. Neither DF nor LF is a normative notation, and implementations of CG tools that conform to this dpANS may extend or modify DF or LF to adapt them to specialized applications.

    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:

    These constraints introduce extraneous features that may be important for human factors or computer efficiency, but they are irrelevant to the abstract syntax, the semantics, and the formal operations.


    A.1 Display Form

    The display form (DF) is a concrete representation for CGs that can be printed or displayed on two-dimensional surfaces. It is designed to enhance readability while representing the abstract syntax as closely as possible. Any information about the display form that is not explicitly derived from AS or CGIF is called layout information. Conformance to this dpANS does not require the preservation of layout information across translations to and from CGIF or to and from other conceptual schema languages such as KIF. Following are the basic principles for mapping the abstract form to the 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.

    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:

    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

      Placement of 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.

    Since DF is not normative, a CG tool that conforms to this dpANS may modify or extend DF for particular applications or I/O devices. An application to poultry farming, for example, might display a concept of type Chicken in the shape of a chicken.


    A.2 Linear Form (LF)

    The following EBNF rules define a recommended context-free syntax of the linear form (LF). The starting symbol is CG, which represents a linear representation of a conceptual graph. The referent field, which is common to both the linear form and the display form, is defined in Section 7.2. To minimize dependencies on implementation-dependent encodings, these rules contain no character constants. The symbol BeginConcept, for example, which is normally represented by the left bracket "[", could be redefined as some other symbol if necessary. The recommended print forms are listed in Section 4.5.


    Annex B (Normative) Metalevel Conventions

    Annex B represents the metalevel conventions for EBNF rules and translation rules. None of the notation in this annex appears in CGIF, and none of it is required to be implemented in any CG tools. Annex B is normative only because the metalevel conventions it defines are used to define CGIF in the normative chapters 7, 8, and 9 of this dpANS.


    B.1 Extended BNF Rules

    The syntax of CGIF and LF is specified by metalevel rules written in Extended Backus-Naur Form (EBNF). Each EBNF rule is a context-free grammar rule that has a single category symbol on the left, a defining marker "::=" in the middle, and a defining expression on the right. The following EBNF rule is a metametalevel rule that specifies the syntax of every EBNF rule, including itself:

    
    EBNFRule  ::=  CategorySymbol DefiningMarker DefiningExpression
    
    
    Each EBNF rule defines the category symbol on the left as the name of a class of strings specified by the defining expression on the right. Each defining expression is a regular expression constructed from the following metalevel categories:

    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 this dpANS. 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 this dpANS. 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 this dpANS.

    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.

    No category symbol that appears in an EBNF rule or a translation rule in this dpANS may contain embedded white space. In an English sentence, however, a category symbol whose identifier contains an embedded uppercase letter may be written with white space inserted before that letter, and uppercase letters may be translated to lowercase. For example, the category symbol written "WhiteSpace" in an EBNF rule may be written "white space" in an English sentence.


    B.2 Translation Rules

    The EBNF rules described in Section B.1 specify the syntax of a language, but not its semantics. To specify semantics, the syntactic categories of a source language may be translated to some target language, such as predicate calculus, whose semantics is independently defined. This section defines translation rules, which augment the EBNF rules with variable assignments, tests, and translation sequences. Each translation rule is a sequence consisting of a rule name, a defining marker "::=", a defining expression, a translation marker "=>", and target.

    
    TranslationRule  ::=  RuleName "::=" DefiningExpression "=>" Target
    
    
    A translation rule may be called by passing a source string to a program called a parser, which matches the defining expression to the source string. If the match is successful, the value of the target is returned as the value of the rule call. If the match is unsuccessful or some rule call in the target fails, the rule call is said to fail. The parts of a translation rule are constructed from the metalevel categories of Section B.1 and the following additional categories:

    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.

    Comment.

    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))
    
    
    When this rule is called to parse any string, the category named LeftEnd matches the start of the source string. Then the category named String matches any string of zero or more characters, which it assigns to the variable named Front. In this case, the parser can scan ahead to look for the first occurrence of a line feed "\n" followed by optional white space, another line feed, and any string up to the right end, which it assigns to the variable Back. If the parser fails to find a sequence of two line feeds separated by white space, it assigns the entire source string to Front and leaves Back with the default value "".

    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

    This dpANS is based on the CG syntax and semantics as published in book form [12,14], in three special issues of journals [1,13,17], and in the proceedings of a series of international conferences and workshops [2,3,6,7,8,9,11,15,16]. Conceptual graphs have been recommended as a conceptual schema language [10], and they have been implemented as an intermediate language for relating different conceptual models [5]. Conceptual graphs are semantically equivalent to the Knowledge Interchange Format (KIF), as defined in the dpANS [4]; any information expressed in either KIF or CGs can be automatically translated to the other without loss or distortion.

    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. Genesereth, Michael R., & Richard Fikes, eds. (1998) Knowledge Interchange Format (KIF), draft proposed American National Standard, NCITS.T2/98-004.

    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. Mineau, Guy W., Bernard Moulin, & John F. Sowa, eds. (1993) Conceptual Graphs for Knowledge Representation, Lecture Notes in AI 699, Springer-Verlag, Berlin.

    9. Mugnier, Marie-Laure, & Michel Chein, eds. (1998) Conceptual Structures: Theory, Tools, and Applications, Lecture Notes in AI 1453, Springer-Verlag, Berlin.

    10. 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.

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

    12. Sowa, John F. (1984) Conceptual Structures: Information Processing in Mind and Machine, Addison-Wesley, Reading, MA.

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

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

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

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

    17. Way, Eileen C., ed. (1992) Journal of Experimental and Theoretical Artificial Intelligence (JETAI), Special Issue on Conceptual Graphs, vol. 4, no. 2.