Parallel standards projects for KIF and CGs

sowa <>
Date: Thu, 28 Apr 94 17:29:43 EDT
From: sowa <>
Message-id: <>
To: interlingua@ISI.EDU, kr-advisory@ISI.EDU, srkb@ISI.EDU,
Subject: Parallel standards projects for KIF and CGs
Last week, the ANSI X3T2 Committee met in Kansas City, where they
voted on two proposed new work items:

  1. A proposed standard for the Knowledge Interchange Format (KIF)
     as an interchange format for conceptual schemas.

  2. A proposed standard for Conceptual Graphs (CGs) as a presentation
     format for conceptual schemas.

These two standards will be developed in parallel as semantically
equivalent representations.  No one will be required to use either
of them for internal processing, for interchange, or for presentation.
However, those who choose to use KIF for interchange can be assured that
whatever they interchange can be presented in CG form and vice-versa.

The KIF draft standard will be based on the June 1992 KIF document
with some additions to represent types.  The CG draft standard will
be based on a version to be discussed and agreed upon at the
ICCS'94 (International Conference on Conceptual Structures), which
will be held in August at the University of Maryland.

In Kansas City last week, Mike Genesereth and I discussed a number
of issues that have been raised on these email lists during the past
year or so.  Following is my summary of my interpretation of what we
had agreed upon (both in KC and in earlier discussions elsewhere):

 1. Types will be going into KIF as syntactic extensions without
    changes to the semantics.  That means that the following
    notation for a cat on a mat

    (exists (?x ?y) (and (cat ?x) (mat ?y) (on ?x ?y))

    can be written in the following form (or perhaps with
    slightly different parenthesization -- check with mrg):

    (exists ((?x cat) (?y mat)) (on ?x ?y))

 2. Mike does not want to define Proposition as a built-in KIF type.
    However, he has no objections to anyone else adding such a type
    to their ontology.  I have been using the types Proposition and
    Situation in conceptual graphs, and I plan to define them in
    terms that can be translated to quoted KIF expressions.

 3. We discussed the check-in/check-out problem; i.e., since KIF
    and CGs are highly expressive, it is easy to map something into
    KIF or CGs, but there is no guarantee that the result will be
    mappable back into other languages that are less expressive.
    Our recommendation is to define subsets of logic with clearly
    defined expressive power and where adherence to the subset can
    be checked with a simple syntactic parse.  Examples of such
    subsets may include

    a) Ground-level atomic propositions, e.g. (loves bill mary)

    b) Existential-conjunctive logic, e.g.
       (exists (?x woman) (loves bill ?x))

    c) Horn-clause or "pure Prolog" subset

    d) KRSS

    e) Full first-order logic, but no metalanguage

    f) FOL plus metalanguage

    g) Ground-level atomic metalanguage, e.g. "The relation
       greater-than is transitive."

    These subsets will be partially ordered; e.g. (b) includes (a),
    and (c) includes (a), but neither (b) nor (c) includes the other.

 4. The question of supersets of KIF and/or CGs for "true" HOL,
    modal logic, fuzzy logic, etc., has also been debated on these
    email lists for a long time.  Many, if not all, of those supersets
    can be defined using the metalanguage capabilities.  This is a
    task that Mike and I believe can be done.  And it should be
    undertaken during the next two years while the draft standards
    are out for comment and review.

One comment about standards:  They are voluntary.  No one is
obligated to adopt them.  And they are not frozen.  ANSI has a
rule that every standard must be reaffirmed every 5 years.
If the committee that originally developed a standard does not
reaffirm it, then it stops being an approved ANSI standard.

Furthermore, the standardization process takes a couple of years
with open, public review at every step of the way.  Anyone who
objects is welcome to raise the objections at any and every
committee meeting.  Gio Wiederhold said that he would be willing
to support academic researchers who would like to become involved
with the standards process.  Anyone who does not like standards
can check with Gio for support to attend the meetings and vote
against KIF and/or CGs and to lobby with the other committee
members to get them to vote against also.

The X3T2 Committee also voted to change its name from Data Interchange
to the new name Information Interchange and Interpretation.  This new
name indicates that the scope of X3T2 is broader than just data, and it
includes the semantics (interpretation) as well.

Following are two documents that were sent from X3T2 to the ANSI
Operations Management Committee (OMC).  The first is a note about
the recent reorganization of X3T2 to include the expanded work on
conceptual schemas, including the new work items on KIF and CGs
and the work on conceptual schemas that had been done in X3H4.
The second is a Standing Document #3 (SD-3), which is a proposed
new work item for a CG standard.  I don't have an electronic copy
of the SD-3 for KIF, but Mike could send that to the list.

John Sowa


Response to OMC Regarding Re-Organization of the X3T2 Program of Work

To convey the broadened program of work of X3T2 and the deepened focus
on conceptual schemas and CSMFs, X3T2 is proposing to OMC that the name
of its TC be officially changed to "Information Interchange and
Interpretation". This recommendation was approved at the April meeting
of X3T2 by an unanimous vote.

After studying its current program of work, as well as an existing project
transferred from X3H4, the assignment by OMC to X3T2 of a liaison project
for the new international project on Conceptual Schema Modelling
Facilities (CSMF) under SC21 WG3, and proposals for new projects, X3T2
intends to organize its standards development work as follows:

1. The new liaison project #1043-L Conceptual Schema Modelling
Facilities (CSMF) will be the primary focus of the X3T2 ad hoc group on
conceptual schemas. This project involves the development of standards
for a generic conceptual schema modelling facility. The terms of
reference for this project are specified in SC21 N8060.  As the U.S. TAG
for this work, X3T2 intends to make significant technical contributions
and has offered to provide the co-editor for the CSMF standard.

2. X3T2's existing project #689-D involves a specialized CSMF for data
interchange. This project will remain in X3T2, and will be a one of several
secondary projects handled under the ad hoc group on conceptual schemas.
However, this standard will now be handled as a specialization of the
generic CSMF standard. This is analogous to the relationship between the
generic standard for Remote Data Access (RDA) and its various
specializations. Liaisons will be established or maintained with other
standards development organizations (SDOs) working on distributed
systems and communication protocols.

3. X3H4's project #988-D on normative schema for repository (IRDS) was
approved by OMC for transfer to X3T2 as part of consolidation of CSMF
work in a single U.S. TC (i.e., under a single U.S. TAG). Like project #689-D,
this project will be handled as a specialization of the generic CSMF
standard, and will be another of the secondary projects conducted by the
X3T2 ad hoc group on conceptual schemas. Coordinating liaison will be
established with X3H4 Portable Common Tool Environment (PCTE), as X3H4
PCTE plans to be the X3 TC working on content integration standards for
repositories, specifically using object services. This will ensure that
related specialized CSMF requirements are conveyed to X3T2, and that the
resulting generic CSMF and its repository specialization can be situated
properly in the context of repository technology.

4. X3T2 also intends to submit new SD-3s for other projects related to
conceptual schemas and CSMFs. At present two proposed projects are
being formulated, one dealing with standardization of a format for
exchanging knowledge encodings between conceptual schemas, and another
for a format for [primarily graphical] presentation of the knowledge
represented in conceptual models.  A potential third project is envisioned
to address a format for expressing fact-based knowledge in a conceptual
model using a stylized form of natural language sentences.

Other projects not related to conceptual schemas or CSMFs will continue
to be progressed by X3T2 as before.

Proposed New SD-3 for Conceptual Graphs



1.1 Title


1.2 Proposer

John F. Sowa
State University of New York (SUNY) Binghamton

1.3 Date Submitted

April 22, 1994

1.4 Project Type

D - The development of the standard will be done within an X3 committee.
The standard may also be progressed through ISO upon establishment of a
corresponding international work item; in that case, the proposers will
apply for a change of status to an international liaison project.


2.1 Needs

International standards work in the area of conceptual schema modelling
facilities (CSMF) has identified a strong need for specialized formats
tailored to the presentation of knowledge in conceptual models.  One such
presentation format desired by many users is a readable graphical format
for acquiring and presenting a conceptual model to both end users and
information technology professionals.  A complementary, equivalent linear
format is needed for compact storage and abbreviated representations in
textual format.

2.2 Recommended Scope of Standard

The scope of this standard encompasses the syntax of both the graphical
and linear (textual) format of conceptual graphs, as well as their mapping
to a Common Logic Foundation (CLF) for conceptual schema modelling
facilities and to the Knowledge Interchange Format (KIF).

Conceptual graphs are intended to be complementary to both KIF and CLF.
KIF, which is primarily designed for the interchange of knowledge
encodings among computer programs, has a simpler syntax and more
restricted character set than CGs, but it is not as readable for human
users as the graphical CG format.  CLF, which is a version of logic with
the barest minimum number of primitives, has a simpler foundation, but it
is not as convenient for representing complex systems and structures.

2.3 Existing Practice in Area of Proposed Standard

There are currently no standards for presentation formats for the full
range of knowledge represented in conceptual models. This knowledge can
range from simple definitions of entities and attributes to complex
propositions about entities, processes, rules and other constraints, as
well as relationships among these various concepts. Some graphical
formats, such as entity-attribute-relationship modelling languages,
already exist, but they represent only selected aspects or kinds of
knowledge and do not offer the breath of range or expressive power of CGs.

2.4 Expected Stability of Standard with Respect to Current and Potential
Technological Advance

The proposed standard would be based on the original CG syntax which was
first published in 1984 [1] and which is currently being revised to reflect
subsequent use and extension arising from practical application in
industry.  The revised syntax will be available by September 1994. During
the ten-year period from 1984 to 1994, the syntax of conceptual graphs
has evolved with minor additions and extensions as it has been used and
implemented by a world-wide user community.  Its relative stability over
that time is strong evidence that it will remain relatively stable as new
applications are developed.

A recent technical report on Conceptual Schema for the Information
Resource Dictionary System (IRDS) [2] has recommended CGs as the basis
for an initial normative language for the IRDS. The report has been
approved by ANSI X3H4 IRDS, and is being published as an ANSI/X3
technical report. Draft versions of the report have received wide
distribution and review within the ANSI and ISO standards communities
and have received highly favorable responses.


3.1 Type of Document


3.2 Definitions of Concepts and Special Terms

The knowledge represented in conceptual models, as referred to in this
SD-3, means information in the form of logical expressions and sentences,
i.e., negations, disjunctions, rules, quantified formulas, and so forth.
Simple data can be expressed in the form of simple sentences; knowledge
often requires more complex sentences.

3.3 Expected Relationship with Approved X3 Reference Models

3.4 Recommended Program of Work

A significant amount of work on the specification, implementation and use
of the CG language has already been carried out in the course of
preparation of [1],  a series of international workshops on conceptual
structures and conceptual graphs [3], and the on-going work of the PEIRCE
project, a cooperative project of academia and industry.  The September
1994 version of CGs is expected to remain quite stable; and we do not
foresee extensive revisions to the syntax and semantics over the next five
to ten years.

The primary effort proposed here will be: (1) to convert the syntax into
the proper format for a standard, (2) to provide a formal BNF account of
the syntax and basic semantics of the language, and (3) to outline
operational considerations in the use of the language (e.g., the design of
inference procedures).

3.5 Resources

In addition to the members of X3T2 who have expressed a willingness to
participate in this project, there is interest on the part of a number of
participants in the PEIRCE project to review, comment on, and otherwise
support this standards development work.  John Sowa is being proposed as

3.6 Recommended X3 Development Technical Committee

It is recommended that this project be assigned to X3T2, as X3T2 is the
U.S. TAG for standards efforts related to conceptual schemas and
conceptual schema modelling facilities.

3.7 Anticipated Frequency and Duration of Meetings

The task group will meet to work on this project on the same meeting
schedule as the X3T2 plenary (ca. quarterly), supplemented with other
meetings as required.  Interim preparation and review work will be
supported by electronic mail.

3.8 Target Date for Working Draft of Standard

A Working Draft of an ANSI standard will be produced by December 31,
1994.  If there is corresponding international work prior to completion of
the Working Draft ANSI standard, U.S. efforts will be coordinated with
that work.

3.9 Estimated Useful Life of Standard

The expected lifetime of this standard will be at least ten years.  It is
expected that the standard will require minor annual revision to keep pace
with continuing developments in conceptual modelling and other aspects
of knowledge technology.


4.1 Impact on Existing User Practices and Investments

This standard will have a positive impact in that it will enable users to
better acquire and present knowledge in the form of conceptual models.
The impact will be on both end users and information technology
professionals such as systems analysts and knowledge engineers.

4.2 Impact on Supplier Products and Support

Vendors will be able to use this standard as the basis for designing and
developing graphical user interfaces (GUIs) to conceptual schema
modelling facilities and other knowledge technologies.

4.3 Techniques and Costs for Compliance and Verification

Compliance with the syntax of CGs will be readily and automatically
determinable, as CG syntax is simple and clearly definable in the standard.

4.4 Legal Considerations

No unusual legal considerations are known as this time.

o Copyrights - no copyrighted material would be used in the standard
without first obtaining the rights to its use.

o Patents - no patented material will be used in the standard without
first obtaining the rights to its use.

o Restraint of Trade - there are no restraint of trade issues associated
with this project.

o Public Interest - public interest will be served by assuring that
meetings remain open to the public which has a direct interest in this
standard.  All documents produced by or submitted for consideration by
the committee responsible for the proposed standard will be available for
public review through the X3 Secretariat.


5.1 Existing Standards

IS 10032 Reference Model of Data Management (RMDM)
IS 10027 Information Resource Dictionary System (IRDS) Framework
IS 10728 Information Resource Dictionary System (IRDS) Services

5.2 X3 Standards Development Projects

X3T2 Information Interchange and Integration - This project will be
coordinated with all of the following X3T2 projects:

o Project 1043-L, the liaison project to the generic conceptual schema
modelling facility (CSMF) standards project under ISO/IEC

o Project 689-D, a specialized CSMF standard for conceptual schemas for
data interchange;

o Project 988-D, a specialized CSMF standard for conceptual schemas for
repositories; and

o Proposed new project for a Knowledge Interchange Format (KIF) standard
(refer to X3T2-042) for interchanging knowledge encodings between
conceptual schemas.

These projects are all closely related, but each addresses a specific need
and there are no overlaps in the objectives or work efforts.

X3H7 Object Information Management - Features Matrix
X3J21 Formal Descriptive Techniques - Z and VDM
X3H4 Portable Common Tool Environment (PCTE) - Content Model
Specification Guidelines

5.3 X3/SPARC Study Groups


5.4 Other Related Domestic Standards Efforts


5.5 ISO Standards Development Projects

ISO/IEC JTC1 SC21 WG3 Conceptual Schema Modelling Facilities (CSMF)
ISO TC184 STandard for the Exchange of Product data (STEP)
ISO/IEC JTC1 SC7 WG11 Software Engineering
ISO/IEC JTC1 SC30 Open edi - Descriptive Techniques for Business

5.6 Other Related International Standards Development Projects


5.7 Recommended for Coordinating Liaison



[1] J. F. Sowa (1984), Conceptual Structures: Information Processing in
Mind and Machine, Addison-Wesley, Reading, MA.

[2] S. K. Perez and A. K. Sarris, Eds. (to be published in 1994), ANSI/X3
Technical Report on Conceptual Schema for the Information Resource
Dictionary System (IRDS), ANSI, New York, NY.

[3] T. E. Nagle, L. L. Gerholz, and P. W. Eklund, Eds. (1992), Conceptual
Structures: Current Research and Practice, Ellis Horwood Publishing Co.,
New York, NY.