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:

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.

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