Proposed New Work Item
for ISO/IEC JTC1 SC32 WG2
Common Logic (CL)
CL is a framework for a family of logic-based languages:
Purpose: Guarantee that content exchanged between CL-conformant languages has the same semantics in each language.
- 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.
- 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:
- 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.
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 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.
- 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.
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.
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.
- 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
- 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.
- Standardize the common semantics.
- Allow any semantic extensions for research.
- Allow any syntactic notations for R & D.
- Common core can be translated to other notations.
- But researchers are free to explore any extensions.
- Useful extensions may be standardized later.