Common Logic:  A Framework
for a Family of Logic-Based Languages



Proposed New Work Item
for ISO/IEC JTC1 SC32 WG2







 
Common Logic (CL)

CL is a framework for a family of logic-based languages:

  • With a semantics that is a superset of the semantics of many other logic-based languages.

  • With an abstract syntax that can be specialized to the concrete syntaxes of other logic-based languages.

  • Designed to preserve the semantics when information is interchanged among heterogeneous systems.
Purpose:  Guarantee that content exchanged between CL-conformant languages has the same semantics in each language.







 
Concrete Syntaxes

  • Each CL-conformant concrete syntax adds grammar rules to express the abstract syntax in concrete symbols.

  • Three concrete syntaxes included in the CL document:

    • KIF:  Knowledge Interchange Format.

    • CGIF:  Conceptual Graph Interchange Format.

    • CLML:  Common Logic Markup Language (XML based).

  • Every CL feature has a concrete expression in KIF, CGIF, and CLML.

  • Any statement in any other CL-conformant language can be translated to KIF, CGIF, or CLML while preserving the original semantics.








 
Example:  Every cat is on a mat.

  • Conceptual graph display form:

    Every cat is on a mat.

  • CGIF: 
       [Cat: @every*x] [Mat: *y] (On ?x ?y)

  • KIF: 
       (forall ((?x Cat)) (exists ((?y Mat)) (On ?x ?y)))

  • CLML:  (Still in development.)

  • CGIF, KIF, and CLML are normative notations.

  • The CG display form is a readable, but nonnormative graphic version of CGIF.








 
CL Conformance


Requirements for a logic notation L to be CL conformant:

  • For any statement of L, the arrow labeled "specification" determines the corresponding abstract syntax.

  • Left downward arrow determines the denotation of that statement.

  • Right downward arrow determines the denotation of the corresponding abstract syntax.

  • Bottom arrow labeled "identity" shows that the denotations must be identical for the language L to be CL conformant.








 
Market for CL

Facilitate interoperability among logic-based languages used in several areas of IT:

  • Metadata and ontology:
    • Knowledge Interchange Format (KIF).
    • Conceptual Graph Interchange Format (CGIF).
    • Cyc Knowledge Representation Language (CycL).
    • Description Logics (DLs).

  • Semantic web:
    • Resource Definition Facility (RDF).
    • Web Ontology Language (OWL).

  • Specification languages:
    • Unified Modeling Language (UML).
    • Z Formal Specification Notation (Z).








 
Relationship to Z

  • Z has been standardized by ISO/IEC IS 13568.

  • Like CL, Z is a version of FOL with a model-theoretic semantics.

  • Differences between CL and Z:

    • CL semantics is a superset of Z semantics.

    • CL abstract syntax supports a much wider range of notations.

    • CL supports the Universal Resource Identifiers (URIs) specified by the W3C.

    • Both typed and untyped versions of FOL can be CL-conformant, but Z requires strict typing.








 
Type Constraints

  • Type constraints restrict permissible values of variables.

  • Type constraints in logic are similar to type constraints in programming languages.

  • Different versions of logic may have compatible semantics, but different kinds of type constraints.

  • General principle:

    • A statement in a strongly typed logic can be translated to an untyped logic.

    • Reverse translation may be difficult or impossible.








 
Various Type Policies

  • Versions of logic with different policies:
    • RDF:  untyped.
    • Conceptual graphs:  optional types.
    • Z:  strongly typed.

  • CL has an untyped core semantics.

  • But CL can support logics with various type policies.








 
Relationship to
Description Logics

  • Description logics (DLs) are a family of languages used to describe and classify concepts and their instances.

  • DLs express various subsets of FOL, and some express nonmonotonic features that are not in FOL.

  • Some DLs have already been translated to KIF, and those should become CL conformant with little additional effort.

  • New DLs have been designed for the semantic web: 
    DAML + OIL → OWL.








 
Relationship to
the Semantic Web

  • W3C is developing standards for two logic-based content languages:
    • RDF:  Language for expressing relationships.
    • OWL:  Language for expressing constraints.

  • One of the CL developers, Pat Hayes, is also a consultant to the W3C.

  • Pat has influenced the design of RDF and OWL to make them CL conformant.

  • Therefore, the CL semantics is inherited by RDF and OWL.








 
OWL Notations

The full OWL notation is untyped, but its expressive power can be restricted in two ways:

The semantics of each OWL notation is determined by its syntactic specification in terms of the CL abstract syntax.







 
FOL and HOL

  • CL model theory supports first-order logic.

  • But CL allows quantified variables to range over predicates:

    • True higher-order logic allows quantifiers to range over uncountably many possible predicates.

    • But CL restricts quantifiers to those predicates specified in the domain of discourse.

  • Result is an FOL semantics that supports HOL-like features.








 
Expressive Power

  • Different CL-conformant languages may express different subsets of FOL.

  • CL-conformant languages can be classified in a hierarchy of expressiveness.

  • Translation from a less expressive to a more expressive language is always possible; reverse translation is possible only on some subset of the more expressive language.

  • Question of whether a particular translation is possible can be determined by syntactic tests.








 
Status of CL Project

Finished now:

  • Model-theoretic semantics.
  • Specification of the CL abstract syntax.
  • Specification of the concrete syntax of KIF and CGIF.
  • Mappings from RDF, RDFS, and OWL to CL abstract syntax.

Complete working draft is being written:

  • Specification of the concrete syntax of CLML.
  • Methodology for ensuring CL conformance.
  • Clarification and explanation of many details.
  • Bringing documentation up to ISO standards.








 
Research & Development

Have different goals:

  • Developers need a fixed, stable platform.
  • Researchers are always exploring new techniques.

Compromise:

  • Standardize the common semantics.
  • Allow any semantic extensions for research.
  • Allow any syntactic notations for R & D.

Results:

  • Common core can be translated to other notations.
  • But researchers are free to explore any extensions.
  • Useful extensions may be standardized later.