Figure B.1 — CG display form for John is going to Boston by bus.
A conceptual graph (CG) is a representation for logic as a bipartite graph with two kinds of nodes, called concepts and conceptual relations. The Conceptual Graph Interchange Format (CGIF) is a fully conformant dialect of Common Logic (CL) that serves as a serialized representation for conceptual graphs. This annex specifies the CGIF syntax and its mapping to the CL semantics. A nonnormative graphical notation, called the CG display form, is used in this document only in examples that illustrate the CG structures. The first example, Figure B.1, shows the display form that represents the sentence John is going to Boston by bus.
Figure B.1 — CG display form for John is going to Boston by bus.
In the display form, rectangles or boxes represent concepts, and circles or ovals represent conceptual relations. An arc with an arrowhead pointing toward a circle marks the first argument of the relation, and an arc pointing away from a circle marks the last argument. If a relation has only one argument, the arrowhead is omitted. If a relation has more than two arguments, the arrowheads are replaced by integers 1,...,n.
The CG in Figure B.1 has four concepts, each with a type label that represents the type of entity to which the concept refers: Person, Go, Boston, and Bus. Two of the concepts have constants that identify individuals: John and Boston. Each of the three conceptual relations has a type label that represents the type of relation: Agnt for the agent of going, Inst for the instrument, and Dest for the destination. The CG as a whole indicates that the person John is the agent of an instance of going with Boston as the destination and a bus as the instrument. Following is the CGIF representation of Figure B.1:
[Go: *x] [Person: John] [City: Boston] [Bus: *y] (Agnt ?x John) (Dest ?x Boston) (Inst ?x ?y)In CGIF, the concepts are represented by square brackets, and the conceptual relations are represented by parentheses. A character string prefixed with an asterisk, such as *x, is a defining label, which may be referenced by the bound label ?x, which is prefixed with a question mark. These strings, which are called coreference labels in CGIF correspond to variables in Common Logic Interchange Format (CLIF). Unless prefixed with the symbol @every, a defining label is translated to an existential quantifier. Following is the equivalent CLIF representation of Figure B.1:
(exists ((x Go) (y Bus))
(and (Person John) (city Boston)
(Agnt x John) (Dest x Boston) (Inst x y)))
As this example illustrates, the differences between CGIF and CLIF result
from the graph structure: the nodes of the graph have no implicit
ordering, and the coreference labels such as *x or ?x
represent connections of nodes rather than variables.
Note that CGIF uses the prefixes * and ?
to distinguish coreference labels from constants, but CLIF does not use
any syntactic convention for distinguishing variables and constants.
Figure B.1 and its representation in CGIF illustrate the extended syntax of CGIF, which adds type labels on concepts and several other syntactic extensions to the core syntax. To convert the extensions of Figure B.1 to the core CGIF, the type labels in the concept nodes are replaced by relations linked to the nodes. The concept [Go:*x], for example, becomes an untyped concept [*x] and a conceptual relation (Go ?x). The concept [Person: John] becomes [:John] (Person John), which may be simplified to just the relation (Person John). Following is the core CGIF and the corresponding CLIF:
[*x] [*y] (Go ?x) (Person John) (City Boston) (Bus ?y) (Agnt ?x John) (Dest ?x Boston) (Inst ?x ?y)
(exists (x y)
(and (Go x) (Person John) (City Boston) (Bus y)
(Agnt x John) (Dest x Boston) (Inst x y)))
To illustrate contexts and logical operators, Figure B.2 shows the display form for the sentence If a cat is on a mat, then it is a happy pet. As in Figure B.1, the rectangles represent concept nodes, but the two large rectangles contain nested conceptual graphs. Any concept that contains a nested CG is called a context; in this example, the type labels If and Then indicate that the proposition stated by the CG in the if-context implies the proposition stated by the CG in the then-context. The Attr relation indicates that the cat, also called a pet, has an attribute, which is an instance of happiness.
Figure B.2 — CG display form for
If a cat is on a mat, then it is a happy pet.
The dotted line connecting the concepts [Cat] and [Pet] is a coreference link, which indicates that they both refer to the same entity. In CGIF, the connection is shown by the defining label *x in the concept [Cat: *x] and the bound label ?x in the concept [Pet: ?x]:
[If: [Cat: *x] [Mat: *y] (On ?x ?y)
[Then: [Pet: ?x] [Happy: *z] (Attr ?x ?z) ]]
In core CGIF, the type labels If and Then are replaced
by a negation symbol ~ in front of the opening bracket,
and the type labels are replaced by monadic relations:
~[ [*x] [*y] (Cat ?x) (Mat ?y) (On ?x ?y)
~[ [*z] (Pet ?x) (Happy ?z) (Attr ?x ?z) ]]
CLIF:
(not (exists (x y) (and (Cat x) (Mat y) (On x y)
(not (exists (z) (and (Pet x) (Happy z) (Attr x z)))))))
In core CGIF, the only quantifier is the existential. In extended CGIF, universal quantifiers may be used to represent the logically equivalent sentence For every cat and every mat, if the cat is on the mat, then it is a happy pet. In extended CGIF, the universal quantifier is represented as @every:
[Cat: @every *x] [Mat: @every *y] [If: (On ?x ?y) [Then: [Pet: ?x] [Happy: *z] (Attr ?x ?z) ]]CLIF:
(forall ((x Cat) (y Mat))
(if (On x y) (and (Pet x) (exists ((z Happy)) (Attr x z)))))
In CGs, functions are represented by conceptual relations called actors. Figure B.3 is the CG display form for the following equation written in ordinary algebraic notation:
y = (x + 7)/sqrt(7)The three functions in this equation would be represented by three actors, which are drawn in Figure B.3 as diamond-shaped nodes with the type labels Add, Sqrt, and Divide. The boxes represent concept nodes, which contain the input and output values of the actors. The two empty concepts contain the output values of Add and Sqrt.
Figure B.3 — CL functions represented by actor nodes
[Number: *x] [Number: *y] [Number: 7] (Add ?x 7 | *u) (Sqrt 7 | *v) (Divide ?u ?v | ?y)In the display form, the input arcs of Add and Divide are numbered 1 and 2 to indicate the order in which the arcs are written in CGIF. Following is the corresponding CLIF:
(exists ((x Number) (y Number))
(and (Number 7) (= y (Divide (Add x 7) (Sqrt 7)))))
No CLIF variables are needed to represent the coreference labels
*u and *v since the functional notation used in CLIF
shows the connections directly.
All semantic features of CL, including the ability to quantify over relations and functions, are supported by CGIF. As an example, someone might say "Bob and Sue are related," but not say exactly how they are related. The following sentences in CGIF and CLIF state that there exists some familial relation r that relates Bob and Sue:
[Relation: *r] (Familial ?r) (#?r Bob Sue) (exists ((r Relation)) (and (Familial r) (r Bob Sue)))The concept [Relation: *r] states that there exists a relation r. The next two relations state that r is familial and r relates Bob and Sue. In CGIF, the prefix # indicates a bound coreference label used as a type label.
The CG abstract syntax is a notation-independent specification of the expressions and components of the conceptual graph core, which is the minimal CG subset capable of expressing the full CL semantics. The semantics of any expression x in the CG core syntax is specified by the function cg2cl(x), which maps x to a logically equivalent expression in the CL abstract syntax. The function cg2cl is recursive, since a CG or its components may be nested inside other components.
Sections 2.1 through 2.11 define the abstract CG syntax, the mapping of the abstract CG syntax to the abstract CL syntax, and the corresponding concrete syntax for CGIF core. Each section includes a formal definition, a mapping to CL, a syntax rule for CGIF concrete syntax, and a comment with explanation and examples. The syntax rules are written in Extended Backus-Naur Form (EBNF) rules, as specified by ISO/IEC 14977 and summarized in Section B.5. For each CGIF syntax rule, the lexical categories of Section A.2.2 shall be assumed. In Section A.2.3.2, the category name includes a category enclosedname of strings enclosed in quotes and a category namesequence of strings that are not enclosed. To avoid possible ambiguities, the category CGname requires that all CLIF name sequences except those in the CGIF category identifier shall be enclosed in quotes:
CGname = identifier | '"', (namesequence - identifier), '"'
| numeral | enclosedname | quotedstring;
identifier = letter, {letter | digit | "_"};
When CGIF is translated to CL, any CGname shall be translated
to a CLIF name by removing any quotes around a name sequence.
CLIF does not make a syntactic distinction between constants and
variables, but in CGIF any CGname that is not used as a defining
label or a bound label shall be called a constant.
The start symbol for CGIF syntax shall be the category text, if the input is a complete text, or the category CG, if the input is a string that represents a conceptual graph.
Definition: A conceptual relation ac=(r,s), in which r shall be a reference called the type label of ac and the arc sequence s=s1,s2 shall consist of an arc sequence s1, called the input arcs, and a single arc s2, called the output arc.
CL: cg2cl(ac) shall be an equation eq: the first term of eq shall be the name cg2cl(s2), and the second term of eq shall be the functional term with operator cg2cl(r) and term sequence cg2cl(s1) with an optional sequence name sqn.
CGIF:
actor = "(", [comment], ["#", "?"], CGname, arcSequence, "|", arc,
[endComment], ")";
Like other conceptual relations, an actor node is enclosed in parentheses.
The symbol # shall mark a bound coreference label that is used
as a type label.
Comment: Although an actor is defined as a special case of a conceptual relation, the CG core syntax restricts an actor to exactly one output arc so that it may be mapped to a CL function. See Figure B.3 for examples of actors and their mapping to CGIF and CLIF. The input arcs may include a sequence name at the end, but no sequence name shall be used for the output arc. The extended CGIF syntax allows actors to have any number of output arcs.
Definition: A reference ar that occurs in an arc sequence of some conceptual relation.
CL: cg2cl(ar) shall be the name n without the marker of the reference ar.
CGIF:
arc = [comment], reference;
Comment: The function cg2cl maps an arc to the name of the reference and omits any marker that distinguishes a bound label.
Definition: A pair as=(s,sqn) consisting of a sequence s of zero or more arcs followed by an optional sequence name sqn.
CL: cg2cl(as) shall be a term sequence ts=cg2cl(s) and the sequence name sqn if present in as. The term sequence ts shall be map(cg2cl,s), where map is a function that applies cg2cl to each arc of the sequence s to extract the name that becomes the corresponding element of the sequence ts.
CGIF:
arcSequence = {arc}, [[comment], "?", seqname];
Any sequence name in an arc sequence as shall be
identical to the sequence name in some existential concept
that is directly contained in a context that contains
the actor or conceptual relation that has the arc sequence as.
Comment: The option of having a sequence name in an arc sequence implies that a conceptual relation may have a variable number of arcs.
Definition: A string cm, which shall have no effect on the semantics of any CGIF expression x in which s occurs.
CL: cg2cl(cm) shall be the substring s of cm that does not include the delimiters "/*" and "*/" of a comment or the opening ";" of an end comment. The string s shall be included in a CL representation for a comment and shall be associated with the CL syntactic expression to which the CGIF expression x is translated. The syntax rules for comment and end comment are identical for core CGIF and extended CGIF.
CGIF:
comment = "/*", {(character-"*") | ["*", (character-"/")]}, ["*"], "*/";
endComment = ";", {character - ("]" | ")")};
The string enclosed by the delimiters "/*" and "*/"
shall not contain a substring "*/". The string of an end
comment may contain any number of ";", but it shall not contain
"]" or ")".
Comment: A comment may occur immediately after the opening bracket of any concept, immediately after the opening parenthesis of any actor or conceptual relation, immediately before any arc, or intermixed with the concepts and conceptual relations of any conceptual graph. An end comment may occur immediately before the closing bracket of any concept or immediately before the closing parenthesis of any conceptual relation or actor. Since the syntax of comments is identical in core and extended CGIF, no additional sytax rules for comments shall be included in Section B.3.
Definition: A pair c=(R,g) where R shall be either a defining label or a set of zero or more references, and g shall be a conceptual graph that is said to be directly contained in c.
CL: cg2cl(c) shall be the sentence s determined by one of the first three options below:
CGIF:
concept = context | existentialConcept | coreferenceConcept;
context = "[", [comment], CG, [endComment], "]";
existentialConcept = "[", [comment], "*", (CGname | seqname),
[endComment], "]";
coreferenceConcept = "[", [comment], ":", {reference}-,
[endComment], "]";
A context shall be a concept that contains a CG;
if the CG is blank, the context is said to be empty,
even if it contains one or more comments.
Any comment that occurs immediately after the opening bracket shall be
part of the concept; any other comments shall be part of the nested CG.
A coreference concept shall contain one or more constants
or bound coreference labels; in EBNF, an iteration followed
by a minus sign with nothing after it indicates at least one iteration.
Comment: A context is represented by a pair of brackets, which serve to limit the scope of quantifiers of the nested CG; an empty context [ ] is translated to CLIF as (and), which is true by definition. An existential concept is represented by a concept such as [*x], which is translated to CLIF as (exists (x) (and)); this sentence asserts that there exists some x. A coreference concept is represented by a concept that contains a set of constants or bound coreference labels, such as [: ?x Cicero Tully ?abcd], which is translated to a conjunction of equations in CLIF:
(and (= x Cicero) (= x Tully) (= x abcd))A coreference concept with just one reference, such as [:?x], would become an empty conjunction (and). Since it has no semantic effect, such a concept may be deleted.
Definition: A triple g=(C,R,A), where C is a set of concepts, R is a set of conceptual relations, and A is the set of arcs that shall consist of all and only those arcs that occur in the arc sequence of some conceptual relation in R. If C and R are both empty, then A is also empty, and g is called a blank conceptual graph.
CL: Let E be the subset of C of existential concepts; and let X be the set of all concepts, conceptual relations, and negations of g except for those in E.
Let B be a Boolean sentence of type conjunction with components consisting of all the sentences cg2cl(x) for every x in X.
If E is empty, then cg2cl(g) is B.
If E is nonempty, then cg2cl(g) is a quantified sentence of type existential with the set of names consisting of the CGname of the defining coreference label of every e in E and with the body B.
CGIF:
CG = {concept | conceptualRelation | negation | comment};
A conceptual graph consists an unordered set of concepts, conceptual
relations, negations, and comments.
Formally, a negation is a pair consisting of a concept
and a conceptual relation that are never separated in CGIF.
Comment: According to this specification, every CG maps to either a quantified sentence of type existential or to a Boolean sentence of type conjunction. If the conjunction has only one component, then the sentence could be simplified to an equality, an atomic sentence, or a Boolean sentence of type negation. If g is blank, the corresponding CLIF is (and), which is true by definition. Although there is no required ordering of the nodes of a CG, some software that processes CGIF may run more efficiently if the defining coreference labels occur before the corresponding bound labels; the simplest way to ensure that condition is to move the existential concepts to the front of any context.
Definition: A pair cr=(r,s), in which r shall be a reference called the type label of cr and s shall be an arc sequence.
CL: cg2cl(ac) shall be an atomic sentence whose predicate is cg2cl(r) and whose term sequence is cg2cl(s).
CGIF:
conceptualRelation = ordinaryRelation | actor;
ordinaryRelation = "(", [comment], ["#", "?"], CGname, arcSequence,
[endComment], ")";
An ordinary conceptual relation has just one sequence of arcs.
An actor partitions the sequence of arcs in two subsequences.
The symbol # shall mark a bound coreference label that is used
as a type label.
Comment: By allowing the type label of a conceptual relation to be a bound label, CGIF supports the CL ability to quantify over relations and functions.
Definition: A pair ng=(c,cr), in which c shall be a concept and cr shall be a conceptual relation whose type label r shall be a constant with CGname Neg. The pair (c,cr) shall be treated as a single unit.
CL: cg2cl(ng) shall be a Boolean sentence of type negation with the component cg2cl(g).
CGIF:
negation = "~", context;A negation shall begin with the symbol ~. Although a negation is formally defined as a pair consisting of a context and a conceptual relation, the two elements of the pair shall not be expressed as separate nodes in CGIF.
Comment: A negation negates the proposition stated by the nested conceptual graph g. For examples, see the CGIF for Figure B.2. The negation of the blank CG, written ~[ ], is always false; the corresponding CLIF is (not (and)).
Definition: A pair r=(m,n) where n is a CG name and m is a marker that shall designate a constant or a bound label.
CL: cg2cl(r) shall be the name n. The marker m shall be ? for a bound label and the empty string "" for a constant.
CGIF:
reference = ["?"], CGname;This syntax of references is identical in core CGIF and extended CGIF. Any CG name that conists of a quoted namesequene shall be translated to a CL name by erasing the enclosing quotes; all other CG names are identical to the corresponding CL names. Sequence names are identical in CLIF and CGIF.
Comment: Since references are identical in core and extended CGIF, no additional syntax rules for references shall be included in Section B.3.
Definition: A set of contexts D associated with a defining label d.
The following terms are used in defining the constraints on defining labels in both core and extended CGIF:
Constraints: The verb contains shall be defined as the transitive closure of the relation directly contains, and it shall satisfy the following constraints in both core and extended CGIF:
The phrase "c contains x" is synonymous with "c directly or indirectly contains x".
Comment: These constraints ensure that for every CGIF sentence s, the translation cg2cl(s) shall obey the CL constraints on scope of quantifiers. Since the constraints on scope are identical in core and extended CGIF, no additional constraints shall be included in Section B.3.
Definition: A context c that is not contained directly or indirectly in any context.
CL: cg2cl(c) shall be text consisting of the sentence cg2cl(g), where g is the conceptual graph directly contained in c. If a CG name n occurs immediately before g in the CGIF specification of the context c, then n shall be the name of the CL text.
CGIF:
text = "[", [comment], "Proposition", ":", [constant], CG,
[endComment], "]";
Since a text is not contained in any context, it shall also be called
the outermost context.
Comment: This syntax rule uses the syntax of extended CGIF, which allows a context to have a type label and a CG name. Since core CGIF syntax is a subset of extended CGIF syntax, text in core CGIF can be used by any processor that accepts extended CGIF. Context brackets may be used to group the concepts and relations of a text into units that correspond to CLIF sentences. That grouping is a convenience that has no effect on the semantics.
Extended CGIF is superset of core CGIF, and every syntactically correct sentence of core CGIF is also syntactically correct extended CGIF. Its most prominent feature is the option of a type label or a type expression on the left side of any concept. In addition to types, extended CGIF adds the following features to core CGIF:
Sections 3.1 through 3.9 define the concrete syntax of extended CGIF and the translation of each extended feature to core CGIF. This translation has the effect of specifying a function CG, which translates any sentence s of extended CGIF to a semantically equivalent sentence CG(s) of core CGIF. The combined functions cg2cl(CG(s)) translate s to a logically equivalent sentence in the CL abstract syntax.
The function CG and other functions for the other CGIF categories are defined by transformation rules whose notation is specified in Section B.5. Two categories, comment and reference, have identical syntax in core and extended CGIF:&nbs; for any comment cm in extended CGIF, comment(cm)=cm; and for any reference r in extended CGIF, reference(r)=r. For any other category X of core CGIF, the strings of category X are a proper subset of the extended CGIF strings of the same category.
Since the definitions in Section B.2 specified the conceptual graph abstract syntax and its mapping to the abstract syntax of Common Logic, they used notation-independent constructs, such as sets. The definitions below specify the mapping from the concrete syntax of extended CGIF to the concrete syntax of core CGIF. Therefore, they are defined in terms of strings and functions that transform strings.
Definition: A string ac that shall contain a comment cm, a reference r called the type label, an arc sequence s1 called the input arcs, an arc sequence s2 called the output arcs, and an optional end comment ecm. The output arcs s2 shall not contain a sequence name.
Translation: A conceptual graph g.
actor(?ac?) -> ?g?;
actor = "(", [comment] ?cm?, (["#", "?"], CGname) ?r?,
arcSequence ?s1?, "|", {arc} ?s2?, [endComment] ?ecm?, ")";
?z1? = map(first,(arcSequence,?s1?));
?z2? = map(first,(arcSequence,?s2?));
?sqn? = third(arcsequence,?s1?);
if (length(?s2?)="0")
?cr? = "(", ?cm?, ?r?, ?z1?, ?sqn?, ?ecm?, ";0-output actor", ")";
elif (length(?s2?)="1")
?cr? = "(", ?cm?, ?r?, ?z1?, ?sqn?, "|", ?z2?, ?ecm?, ")";
else ?cr? = "(", ?cm?, ?r?, ?z1?, ?sqn?, "/*|*/", ?z2?, ?ecm?, ")";
end;
?g? = map(second,(arcSequence,?s1?)), map(second,(arcSequence,?s2?)),
?cr?;
end;
If s2 has no output arcs, cr shall be an ordinary conceptual relation, as defined in Section B.3.7; but to show that cr was derived from an actor, an end comment "0-output actor" is inserted. If s2 has one output arc, cr shall be an actor, but cr differs from ac because the arcs are translated to core CGIF. If s2 has two or more output arcs, cr shall be an ordinary conceptual relation, but the comment "/*|*/" is inserted to distinguish the input arcs from the output arcs. The final rewrite rule puts cr after any conceptual graphs derived from the arc sequences.
Comment: As an example, the combined effect of the transformation rules for actors, arcs, arc sequences, and concepts would translate the following actor node
(IntegerDivide [Integer: *x] [Integer: 7] | *u *v)to a six-node conceptual graph consisting of three concepts and three conceptual relations:
[*x] (Integer ?x) (Integer 7) [*u] [*v] (IntegerDivide ?x 7 /*|*/ ?u ?v)The comment /*|*/ has no semantic effect in core CGIF or CL, but if preserved, it would enable a mapping back to extended CGIF to distinguish the input arcs from the output arcs. If the distinction is important for some application, axioms may be used to state the functional dependencies of the outputs on the inputs. For example, the CL relation that results from the translation of an actor of type IntegerDivide would satisfy the following constraint stated in CLIF:
(exists (Quotient Remainder) (forall (x1 x2 x3 x4)
(iff (IntegerDivide x1 x2 x3 x4)
(and (= x3 (Quotient x1 x2)) (= x4 (Remainder x1 x2))))))
This sentence asserts that there exist functions Quotient
and Remainder that determine the values of the of the third
and fourth arguments of the relation IntegerDivide.
The translation rules would not generate that axiom automatically,
but it could be stated by a CGIF sentence that would be
translated to the CLIF sentence:
[*Quotient] [*Remainder]
[[@every*x1] [@every*x2] [@every*x3] [@every*x4]
[Equiv: [Iff: (IntegerDivide ?x1 ?x2 | ?x3 ?x4)]
[Iff: (?Quotient ?x1 ?x2 | ?x3) (?Remainder ?x1 ?x2 | ?x4)]]]
To show that the existential quantifiers for [*Quotient] and
[*Remainder] take precedence over the universal quantifiers
for the four arguments, a pair of context brackets is used to enclose
the concept nodes with universal quantifiers.
Definition: A string ar that shall contain an optional comment cm and either a reference r, a defining label with CG name n, or a concept c.
Translation: A pair (x,g) consisting of a an arc x and a conceptual graph g.
arc(?ar?) -> ?x?, ?g?;
arc = [comment] ?cm?, (reference ?r? | "*", CGname ?n? | concept ?c?);
if (?r?~= ) ?x? = ?ar; ?g? = ;
elif (?n?~= ) ?x? = ?cm?, "?", ?n?; ?g? = "[*", ?n?, "]";
else ?x? = ?cm?, first(concept(?c?));
?g? = third(concept(?c?));
end; end;
If ar is a reference, x shall be ar unchanged,
and g shall be blank.
If ar contains a defining label, x shall be the
result of replacing the marker * in ar with ?,
and g shall be the concept [*n].
If ar contains a concept c, x shall be
the result of replacing the concept c in ar with
a reference r, and g shall be third(concept(c)).
Comment: As an example, if the arc ar is [Integer], the value of concept([Integer]) would be a CG name, such as g00023, and arc([Integer]) would be the pair consisting of the reference ?g00023 and the conceptual graph [*g00023] (Integer ?g00023).
Definition: A string as that shall contain a sequence s of zero or more arcs followed by an optional sequence name sqn.
Translation: A triple (rs,g,sqn) consisting of a sequence of references rs, a conceptual graph g, and the sequence name sqn.
arcSequence(?as?) -> ?rs?, ?g?, ?sqn?;
arcSequence = {arc} ?s?, [[comment], "?", seqname] ?sqn?;
?rs? = map(first,map(arc,?s?)));
?g? = map(second,map(arc,?s?)));
end;
Comment: The function map(arc,?s?) applies arc to each arc of s to generate a sequence of pairs consisting of a reference and a concept. Then map(first,map(arc,?s?)) extracts the sequence of references from the first element of each pair. Finally, map(second,map(arc,?s?)) extracts the sequence of concepts from the second element of each pair. The option of having a sequence name in an arc sequence implies that a conceptual relation may have a variable number of arcs. An actor may have a variable number of input arcs, but the number of output arcs shall be fixed; therefore, the output arcs shall not have a sequence name.
Definition: A string b that shall contain a context bc, which shall not directly contain a reference or a defining label. The context bc shall have either a prefix "~" and no type label or no prefix and one of the following constants as type label: Either, Equiv, Equivalence, If, Iff, Then.
Translation: A negation ng that shall be negation(b), eitherOr(b), ifThen(b), or equiv(b).
boolean = negation | eitherOr | ifThen | equiv;
negation(?b?) -> ?ng?;
negation = "~[", [comment] ?cm?, CG ?x?, [endComment] ?ecm?, "]";
?ng? = "~[", ?cm?, CG(?x?), ?ecm?, "]";
end;
ifThen(?b?) -> ?ng?;
ifThen = "[", [comment] ?cm1?, "If", [":"], CG ?ante?,
"[", [comment] ?cm2?, "Then", [":"], CG ?conse?,
[endComment] ?ecm1?, "]", [endComment] ?ecm2?, "]";
?ng? = "~[", ?cm1?, CG(?ante?),
"~[", ?cm2?, CG(?conse?), ?ecm1?, "]", ?ecm2?, "]";
end;
equiv(?b?) -> ?ng?;
equiv = "[", [comment] ?cm1?, ("Equiv" | "Equivalence"), [":"],
"[", [comment] ?cm2?, "Iff", [":"], CG ?g1?,
[endComment] ?ecm2? "]",
"[", [comment] ?cm3?, "Iff", [":"], CG ?g2?,
[endComment] ?ecm3? "]", [endComment] ?ecm1? "]";
?ng? = "~[", ?cm1?, "~[", ?cm2?, CG(?g1?),
"~[", CG(?g2?), "]", ?ecm2?, "]",
?cm2?, "~[", ?cm3?, CG(?g2?),
"~[", CG(?g1?), "]", ?ecm3?, "]", ?ecm1?, "]";
end;
eitherOr(?b?) -> ?ng?;
eitherOr = "[", [comment] ?cm?, "Either", [":"],
{[comment], nestedOrs} ?ors?, [endComment] ?ecm?, "]";
?ng? = "~[", ?cm?, nestedOrs(?ors?), ?ecm?, "]";
end;
nestedOrs(?ors?) -> ?g?;
nestedOrs = "[", [comment] ?cm?, "Or", [":"], CG ?ng?,
[endComment] ?ecm?, "]", nestedOrs ?more?
| );
if (?more?= ) ?g? = ;
else ?g? = "~[", ?cm?, CG(?ng?), ?ecm?, "]", nestedOrs(?more?);
end; end;
The rule for nestedOrs recursively processes a sequence of zero or more
boolean contexts of type Or.
If ng contains zero nested Ors, eitherOr(ng) shall be
~[ ], which is false; the corresponding CL sentence
(or) is defined to be false.
Comment: The scope of quantifiers in any of the Boolean contexts shall be determined by the nesting of their translations to core CGIF. Any defining label in a context of type If shall have the nested context of type Then within its scope. For any two contexts directly contained in a context of type Either, Equivalence, or Equiv, neither one shall have the other within its scope.
Definition: A string c consisting of four substrings, any or all of which may be omitted: an opening comment cm, a type field, a referent field, and an end comment ecm.
The referent field of c may contain a defining sequence label with sequence name sqn. If so, the type field of c shall be empty, the defining sequence label may be preceded by "@every", and there shall not be any references or any conceptual graph in the referent field of c.
If no sqn, the type field of c shall contain either a type expression tx and a colon ":" or an optional reference ty called a type label and an optional colon ":". If no sqn, the referent field of c shall contain an optional defining label with CG name df (which may be preceded by "@every"), a sequence of zero or more references rf, and a conceptual graph g, which may be blank. If all the options are omitted, the concept c shall be the string "[]".
Translation: A triple (r,q,g) consisting of a reference or a bound sequence label r, a quantifier q, which shall be "@every" or the empty string, and a conceptual graph g, which shall contain at least one concept.
concept(?c?) -> ?r?, ?q?, ?g?;
concept = "[", [comment] ?cm?,
( (typeExpression ?tx?, ":"
| ["#", ("?", CGname) ?ty? | CGname ?ty?], [":"]),
[["@every"] ?q?, "*", CGname ?df?], {reference} ?rf?, [CG] ?x?
| ["@every"] ?q?, "*", seqname ?sqn?
), [endComment] ?ecm?, "]";
if (?sqn?~= ) ?r? = "?", ?sqn?; ?g1? = "[", ?cm?, "*", ?sqn?, ?ecm?];
elif (?df?~= ) ?r? = "?", ?df?; ?g1? = "[", ?cm?, "*", ?df?, ?ecm?];
if (?rf?~= ) ?g2? = "[", ":", ?r?, ?rf?, "]"; end;
elif (?rf?~= ) ?r? = first(?rf?);
?g2? = "[", ?cm?, ":", ?rf?, ?ecm?, "]";
else ?df? = gensym(); ?r? = "?", ?df?;
?g1? = "[", ?cm?, "*", ?df?, ?ecm?, "]";
end;
if (?tx?~= ) ?b? = second(typeExpression(tx));
?gx? = third(typeExpression(tx));
?g3? = substitute(?r?,?b?,?gx?);
elif (?ty?~= ) ?g3? = "(", ?ty?, ?r?, ")"; end;
elif (?x?~= ) ?g4? = "[", ?x?, "]";
end;
?g? = ?g1?, ?g2?, ?g3?, ?g4?;
end;
Four options are permitted in the type field: a type expression
tx, a bound coreference label prefixed with "#",
a constant, or the empty string; a colon is required after tx,
but optional after the other three.
The rewrite rules move features from the concept c
to four strings, which are concatenated to form the conceptual graph
g: g1 is an existential concept with the defining
label from c or with a label generated by gensym()
if no defining label or reference occurs in c;
g2 is a coreference concept if any references occur in c;
g3 is either a conceptual relation with a type label ty
or a conceptual graph generated from a type expression tx;
and g4 is a context containing any nonblank CG x.
Any comments cm and ecm are placed in the first nonblank
concept, which shall be either g1 or g2.
Comment: To illustrate the translation, the sentence A pet cat Yojo is on a mat could be represented in extended CGIF with two concept nodes in the arc sequence of a conceptual relation:
(On [@*x (Pet ?x) (Cat ?x): Yojo] [Mat])To generate the equivalent core CGIF, the concepts are removed from the arc sequence. In their place, references are left to link them to the concepts, which are expanded by the above rewrite rules. Following is the resulting core CGIF:
[: Yojo] (Pet Yojo) (Cat Yojo) [*g00238] (Mat ?g00238) (On Yojo ?g00238)The CG name Yojo is the reference for the first concept, and the CG name g00238 for the mat is generated by gensym(). See Section B.3.9 for a discussion of the type expression and its translation. The translation by cg2cl would translate the core CGIF to the abstract syntax, which would be expressed by the following CLIF:
(exists (g00238) (and (= Yojo Yojo) (Cat Yojo)
(Mat ?g00238) (On Yojo ?g00238)))
A coreference concept with only one reference, such as [: Yojo],
has no effect on the truth or falsity of the sentence.
It could be deleted by an optimizing compiler,
unless it is needed as a container for comments.
Definition: A string cg consisting of an unordered sequence of substrings that represent concepts, conceptual relations, booleans, and comments.
Translation: A conceptual graph g.
CG(?cg?) -> ?g?;
CG = {concept | conceptualRelation | boolean | comment};
if (first(sortCG(?cg?)~= )
?g? = "~", "[", first(sortCG(?cg?)),
"~", "[", second(sortCG(?cg?), "]", "]";
else ?g? = second(sortCG(?cg?);
end; end;
sortCG(cg) shall be the pair (g1,g2), where g1 is
the conceptual graph derived from all the universally quantified concepts
in cg and g2 is the conceptual graph derived from all other
concepts, conceptual relations, and comments in cg.
sortCG(?cg?) -> ?g1?,?g2?;
sortCG = ( (concept ?c? | conceptualRelation ?x?
| boolean ?x? | comment ?x?), sortCG ?rem?
| );
if (?c?= ) ?cg2? = CG(?x?));
elif (second(concept(?c?)) = "@every")
?cg1? = third(concept(?c?));
else ?cg2? = third(concept(?c?));
end;
?g1? = ?cg1?, first(sortCG(?rem?)); ?g2? = ?cg2, second(sortCG(?rem?));
end;
Comment: If there are no concepts containing universal quantifiers in the input string, the result shall be a single string in core CGIF that concatenates the results of translating each node independently of any other node. But if the input string contains any universal concepts, the output string shall be a nest of two negations. The outer context shall contain the translations of all the universal concepts, and the inner context shall contain the translations of all other nodes in the input.
Definition: A string cr that represents an ordinary conceptual relation or an actor.
Translation: A conceptual graph g, which shall be either ordinaryRelation(cr) or actor (cr).
conceptualRelation = ordinaryRelation | actor;
ordinaryRelation(?cr) -> ?g?;
ordinaryRelation = "(", [comment] ?cm?, (["#", "?"], CGname) ?r?,
arcSequence ?s?, [endComment] ?ecm?, ")";
?g? = map(second,(arcSequence,?s?)),
"(", ?cm?, ?r?, map(first,(arcSequence,?s?)),
third(arcSequence(?s?)), ?ecm?, ")";
end;
The first line of the rewrite rule extracts
a conceptual graph from the arc sequence s.
The second line adds the opening comment, type label,
and arc sequence of a conceptual relation.
The third line adds the sequence name, if any, the end comment,
and the closing parenthesis of the conceptual relation.
Comment: As an example, the conceptual relation (On [Cat: Yojo] [Mat]) would be translated by the rules for conceptual relations, arcs, arc sequences, and concepts to generate the following conceptual graph expressed in core CGIF:
[: Yojo] (Cat Yojo) [*x] (Mat ?x1) (On Yojo ?x1)
Definition: A context c that is not contained directly or indirectly in any context.
Translation: A context cx.
text(?c?) -> ?cx?;
text = "[", [comment] ?cm?, "Proposition", ":", [CGname] ?n?,
CG ?g?, [endComment] ?ecm?, "]";
?cx? = "[", ?cm?, "Proposition", ":", ?n?, CG(?g?), ?ecm?, "]";
end;
Definition: A string tx containing a CG name n and a conceptual graph g.
Translation: A pair (b,g), consisting of a bound label b and a conceptual graph g.
typeExpression(tx) -> ?b?,?g?; typeExpression = "@", "*", CGname ?n?, CG ?g?; ?b? = "?", ?n?; end;If a concept c contains a type expression, the rewrite rules that specify concept(c) use the function substitute(?r?,?b?,?g?) to substitute some reference r for every occurrence of b in g.
Comment: A type expression corresponds to a lambda expression in which the CG name n specifies the formal parameter, and the conceptual graph g is the body of the expression. If a concept c contains a type expression, the transformation rules that process c shall substitute a reference derived from c for every occurrence of the bound label ?n that occurs in g.
That combination defines a function cg2cl, which translates any sentence s of core CGIF to a logically equivalent sentence cg2cl(x) of Common Logic. To specify the translation from extended CGIF to core CGIF, Section B.3 uses a combination of EBNF syntax rules plus the rewrite rules specified in Section B.5.3 to define a function ex2cor, which translates any sentence s of extended CGIF to a logically equivalent sentence CG(s) of core CGIF.
The syntax of both core and extended CGIF is defined by rules in Extended Backus-Naur Form (EBNF) rules as specified by ISO/IEC 14977 and summarized in Section B.5.1. To specify the translation from core CGIF to Common Logic, Section B.2 uses a combination of EBNF rules and mathematical notation supplemented with English. To specify the translation from extended CGIF to core CGIF, Section B.3 uses a combination of EBNF rules and the rewrite rules defined in Section B.5.2. The syntax rules in Annex B presuppose a lexical analysis stage that has subdivided the text into tokens; at any point where a comma occurs in an EBNF rule, zero or more characters of white space may occur in the input text.
The specifications in Annex B use only the following subset of the features specified by the EBNF standard:
Terminal symbol. Any string enclosed in either single quotes or double quotes. Examples:
"This is a quoted string." 'and so is this'
Nonterminal symbol. A name of a category in a syntax rule. For example, the following syntax rule contains two nonterminal symbols, one terminal symbol '";"', a defining symbol "=", a concatenation symbol ",", and a terminator symbol ";".
syntaxRule = expression, ";";
Option. An expression enclosed in square brackets. It specifies zero or one occurrence of any string specified by the enclosed expression. Example:
[ "This string may or may not occur." ]
Iteration. An expression enclosed in curly braces. It specifies zero or more occurrences of any string specified by the enclosed expression. Example:
{ "This string may occur many times." }
Concatenation. Two or more terms separated by commas.
"Two kinds of quotes: ", "'", " and ", '"', "."
Exception. Two terms separated by a minus sign -, which specifies any string specified by the first term, but not the second. The following example specifies a sequence of zero or more digits that does not contain "6":
{digit} - 6
Group. An expression enclosed in parentheses and treated as a single term. The following group encloses an exception that specifies a sequence of one or more digits by excluding the empty term:
({digit} - )
Alternatives. Two or more concatenations separated by vertical bars. Example:
"cat", "dog" | "cow", "horse", "sheep" | wildAnimal
Special sequence. Any string enclosed by question marks. These sequences shall not affect the syntax specified by the syntax rules, but they may be used to copy strings analyzed by a syntax rule for later use by the rewrite rules specified in Section B.5.2. Example:
?sqn?
Syntax rule. A nonterminal symbol followed by "=" followed by an expression and ending with ";". The following syntax rules define the syntax of the syntax rules used in Annex B.
syntaxRule = expression, ";";
expression = alternative, {"|" alternative} | term, "-", term;
alternative = term [variable], {"," term [variable]};
term = terminal | nonterminal | "[", expression, "]"
| "{", expression, "}" | "(", expression, ")" | empty;
terminal = "'", ({character - '"'} - empty), "'"
| '"', ({character - "'"} - empty), '"';
nonterminal = identifier;
variable = "?", identifier, "?";
identifier = letter, {letter | digit | "_"};
empty = ;
These rules specify a subset of the syntax rules specified in Section 8.1 of the ISO/IEC 14977 standard. The rules imply that "," has higher precedence than "|", which has higher precedence than "=". Parentheses may be used to override the precedence or to make the grouping more obvious.
Each transformation rule shall define a function that analyzes an input string and returns a sequence of one or more output strings. A transformation rule shall have three parts: a header, a syntax rule as defined in Section B.5.1, and zero or more rewrite rules. The first string in a header shall specify the name of the function, which shall also be the name of the nonterminal symbol defined by the syntax rule. The header shall also specify a variable whose value shall be the input string to be analyzed by the syntax rule, and it shall specify a sequence of one or more output variables. If the syntax rule successfully analyzes the input string from beginning to end, the rewrite rules, if any, are executed. Following are the syntax rules that define the syntax of the transformation rules; transRule is the start symbol.
transRule = header, syntaxRule, {rewriteRule}, "end", ";";
header = nonterminal, "(", variable, ")", "->",
variable, {"," variable};
rewriteRule = assignment | conditional;
assignment = variable, "=", rewriteExpr, ";";
conditional = "if", condition, ({rewrite rule} - empty),
["elif", condition, ({rewrite rule} - empty)],
["else", ({rewrite rule} - empty)], "end;"
condition = "(", test, {"&", test}, ")";
test = rewriteTerm, ["~"], "=", rewriteTerm;
test = rewriteTerm, ["~"], "=", rewriteTerm;
rewriteExpr = rewriteTerm {"," rewriteTerm};
rewriteTerm = terminal | variable | funTerm;
funTerm = identifier, "(", [funTerm, {"," funTerm}, ")";
The following the nonterminal symbols shall be defined as
in Section B.5.1: syntaxRule, terminal, nonterminal,
variable, identifier, empty.
The function defined by a transformation rule shall translate the input string to the sequence of values of the output variables by copying substrings from the input and executing rewrite rules to transform those strings. The execution shall be determined by the following procedure:
According to this specification, some transformation rules may have no rewrite rules. The following rule, for example, defines an identity function, whose output is identical to its input:
identity(?s?) -> ?t?;
identity = {character} ?t?;
end;
The input string s is parsed by the syntax rule as a string
of zero or more characters. That string is assigned to t,
which becomes the output of the function.
The value assigned to a variable as a result of the parse is always some substring from the input. Except for the identity function, the output values generated by the rewrite rules for any syntactic category are often very different from any substring of the input. As an example, the transformation rule named negation translates a negation from extended CGIF to core CGIF:
negation(?b?) -> ?ng?; negation = "~[", [comment] ?cm?, CG ?x?, [endComment] ?ecm?, "]"; ?ng? = "~[", ?cm?, CG(?x?), ?ecm?, "]"; end;The strings for the opening comment cm and the ending comment ecm are copied unchanged from input to output. But the nested CG, whose input string x is in extended CGIF, is very different from the core CGIF output of CG(x). The transformation rules for the syntactic categories of extended CGIF behave like compilers that translate input strings for extended CGIF categories to output strings in core CGIF.
Any function defined by a transformation rule may be used in a rewrite rule. It may even be used recursively in the same transformation rule that defines it. In addition to the functions defined by transformation rules, the following seven functions shall be available for use in processing strings or sequences in any rewrite rule.
first(s) shall return the first or only element of a sequence s. If length(s)="0", first(s) shall be empty.
gensym() shall return a string that represents a CGname that shall be different from any other CGname in the current text. Each time gensym() is invoked, the string it returns shall also be different from any string it had previously returned.
length(s) shall return the length of the sequence s as a string of one or more characters that represent the decimal digits of the length. If s is empty, length(s) shall be "0". If s is a single element, length(s) shall be "1".
map(f,s) shall apply a function f to each element of a sequence s in order to return the sequence of values of f(x) for each x in s.
second(s) shall return the second element of a sequence s. If length(s)<"2", second(s) shall be empty.
substitute(s,t,x) shall return the result of substituting the string s for every occurrence of the string t in the string x. If t does not occur in x, substitute(s,t,x) shall be x.
third(s) shall return the third element of a sequence s. If length(s)<"3", third(s) shall be empty.