[ba-ohs-talk] Fwd: CG: Common Logic Standard
FYI,... (01)
>From: "John F. Sowa" <sowa@bestweb.net>
>To: standard-upper-ontology@IEEE.org, cg@cs.uah.edu
>
>On March 21 and 22, Mike Genesereth hosted a meeting at Stanford
>University of the working group on the proposed ISO standards for
>the Knowledge Interchange Format (KIF) and Conceptual Graphs (CGs).
>The minutes of the meeting are posted at the following URL:
>
> http://cl.tamu.edu/minutes/stanford-minutes.html
>
>Since the minutes are rather brief, they may be cryptic to those
>who did not attend. I'm writing this note to expand some of the
>remarks and their implications.
>
>One of the significant decisions was to choose a new name,
>Common Logic (CL), for the proposed standard. The intent is to
>reduce any bias toward the two starting notations, KIF and CGs,
>and to emphasize the common basis in first-order logic, as it
>was originally developed by Frege, Peirce, Schroder, Peano, and
>many others during the late 19th and early 20th centuries.
>
>In keeping with that decision, CL will be defined by an abstract
>syntax, which specifies the major categories, such as Quantifier,
>Negation, and Conjunction, without specifying any concrete symbols
>for writing them. At the abstract level, even the ordering is
>left undefined so that there is no bias toward a prefix notation
>such as KIF, an infix notation such as predicate calculus, or a
>graph notation such as CGs (or Peirce's original existential graphs).
>
>Since it is impossible to write a purely abstract syntax, the CL
>standard will also contain grammars for three concrete syntaxes:
>KIF, CGIF (the CG interchange format), and traditional predicate
>calculus (TPC) with a Unicode encoding of the commonly used symbols.
>Each of those grammars will specify how the abstract categories are
>mapped to the printable (or computer representable) symbols of their
>notations. Any of the three concrete notations can be mapped into
>any of the others by reversing the mapping from concrete to abstract
>in one notation and then mapping from abstract to concrete in the
>other notation.
>
>The standard will also contain a version of model theory defined
>in terms of the abstract syntax. The model theory will specify
>the truth conditions for any abstract statement, and any conforming
>concrete statement in any syntax that is mapped from that abstract
>statement would be required to have exactly the same truth conditions.
>This requirement will ensure identical semantics for statements
>represented in any concrete syntax that conforms to the standard.
>
>Besides the three concrete syntaxes that are currently planned for
>the standard, we also discussed plans for an XML-based syntax that
>could be mapped directly to the abstract syntax. For example, the
>abstract category Conjunction would be expressed differently in
>each of the three concrete syntaxes. Instead of giving a separate
>mapping to XML from each of the concrete syntaxes, it would be
>simpler to map the abstract category directly to the XML form
><conjunction>... </conjunction> without specifying which of the
>three concrete syntaxes was the original source or the intended
>target of the information.
>
>Although the CL project grew out of a collaboration between the
>KIF and CG communities, we hope that the CL standard can be used
>for many other languages that have a declarative semantics, such
>as RDF, UML, DAML, or Topic Maps. Any language that can be mapped
>to and from the CL abstract syntax would automatically inherit the
>same model-theoretic semantics and would therefore be semantically
>compatible and interoperable with software based on any other
>languages that adopt the CL semantics.
>
>Since different languages have different expressive powers, it
>might not be possible to map every feature of the abstract syntax
>into each of them. For KIF, CGIF, TPC, and the XML form, every
>feature of the abstract syntax will be expressible in the concrete
>notations. Other declarative languages, however, might not have
>the same expressive power. Such languages could only express a
>subset of the statements expressible in the abstract syntax.
>
>Several other questions were also discussed and tentative answers
>were considered. Following are the questions, and the most widely
>accepted answers. Further discussion of the implications of the
>various options is encouraged.
>
> Q: How will the CL standard relate to the W3C standards for
> symbols, formats, and naming conventions?
>
> A: The CL standard will be compatible with all the accepted W3C
> standards. Following are some of the issues:
>
> 1. There will be an XML representation of the abstract categories,
> which will conform to all accepted W3C standards. There may
> also be XML representations of the concrete syntaxes as well.
>
> 2. The basic symbol set of both KIF and CGIF does not require
> any symbols beyond the basic 7-bit ASCII, but it will permit
> Unicode character strings and identifiers with conventions
> similar to Java. TPC notation will require Unicode for the
> special logical symbols, but they could also be represented,
> as in HTML and XML, by symbols like ∀ or ∃.
>
> 3. The globally unique URIs specified by the W3C could be used
> in any concrete CL syntax. URIs may have two parts:
>
> doc-id#frag-id
>
> where the doc-id identifies a document and the frag-id
> identifies a fragment within the document. For any concrete
> CL notation (KIF, CGIF, TPC, or XML-CL), the doc-id would
> denote some document that contains a collection of
> statements in that notation; and the frag-id would be
> some identifier defined and used in those statements. For
> references within a CL document, only the frag-id would be
> used; but global references to other documents would use
> both the doc-id and the frag-id.
>
> Q: Will CL support unrestricted quantifiers, sorted quantifiers,
> or restricted quantifiers?
>
> A: Some version of sorted or restricted quantification will be
> supported. As a result of previous collaboration between the
> KIF and CG communities, the KIF 3.0 document provided a notation
> for restricted quantifiers to represent the type lables in CGs.
> As an example, the following CGIF represents the English sentence
> "A cat is on a mat":
>
> [Cat: *x] [Mat: *y] (On ?x ?y)
>
> This graph can be translated to the following statement in
> KIF 3.0 notation:
>
> (exists ((?x Cat) (?y Mat)) (On ?x ?y))
>
> In KIF 3.0, Cat and Mat are treated as monadic predicates,
> and the above statement is semantically identical to the
> following version, which uses unrestricted quantifiers:
>
> (exists (?x ?t) (and (Cat ?x) (Mat ?y) (On ?x ?y))
>
> However, some implementers, such as Mark Stickel, distinguished
> the sort identifiers from the monadic predicates in order to
> do better syntax checking and to allow improved performance
> during the theorem-proving process.
>
> The consensus was that some version of sorted or restricted
> quantification will be supported by CL, but no decision was
> made on the question of strict sorting (which would permit
> compile-time checking instead of run-time checking).
>
> Q: Will CL support contexts? Will nested contexts be permitted?
> If so, what is the semantics?
>
> A: CL will provide a mechanism for breaking up a collection of
> statements into contexts, which can be nested arbitrarily deep.
> The CL identifiers will use segmented notation to specify the
> nested levels of contexts. For example, an identifier, such as
> abc.def.xyz would represent an entity xyz in context def, which
> is nested in context abc. The identifier "abc.def.xyz" would
> correspond to a frag-id within a CL document. If preceded by
> a doc-id, it could refer to something in a different CL document.
>
> No decision was made on the separator between segments. Another
> suggestion was to use the slash, as in abc/def/xyz. The semantics
> of the contexts is determined by the metalevel facilities of CL.
>
> Q: What are the metalevel facilities of CL?
>
> A: The details of the metalevel are still undecided, but various
> participants in the working group have proposals, which they
> will present later. Following are some of the suggestions:
>
> 1. An important reason for contexts is grouping, so that
> one or more statements or graphs can be identified by
> a frag-id. Such grouping would be transparent and would
> not affect the semantics -- i.e, multiple statements in a
> context are impliclitly connected by conjunction, whether
> or not they happen to be grouped in various ways.
>
> 2. A group of statements in a context may be the argument of
> a predicate or relation. The meaning of that context is
> determined by the axioms that define the relation. Those
> axioms must be in a context outside the context that is
> contained in the argument.
>
> 3. Tarski's hierarchy of metalevels, as he defined it in his
> 1933 paper, avoids the usual paradoxes about metalevel
> references. Some semantics along those lines is being
> considered, but other alternatives may also considered.
>
> 4. The metalevel operations will be able to refer to the
> named contexts and their contents as characterized by the
> abstract syntax. Since the abstract syntax is independent
> of any concrete syntax, it would be possible for a KIF or
> CGIF statement to refer to the abstract parts of a context
> independently of the concrete syntax that was used to define
> the contents of that context.
>
>For other topics considered, see the minutes. For any other questions,
>please reply to the above email lists for discussion.
>
>John Sowa (02)