CMU Artificial Intelligence Repository
COLAB: Knowledge Representation and Compilation Laboratory
areas/kr/systems/colab/
This directory contains the COmpilation LABoratory (COLAB).
COLAB is a hybrid knowledge representation system emphasizing the
horizontal and vertical compilation of knowledge bases. It has been
designed as a COmpilation LABoratory aiming at a synergetic
collaboration of different knowledge representation and reasoning
formalisms. It is comprised of subsystems dealing with different
kinds of knowledge and that can also be used as stand-alone systems.
The COLAB representation architecture splits into two main parts, an
affirmative part, sometimes also called `assertional', and a taxonomic
part.
The affirmative part provides efficient reasoning with different kinds
of relational or functional knowledge using tailored inference
engines. For affirmative knowledge represented as constraint nets
COLAB supplies constraint propagation techniques (CONTAX). Relational
knowledge in the form of Horn rules is processed by forward (FORWARD)
and backward (RELFUN) chaining. The backward component is also suited
for expressing (non-deterministic) functional dependencies. Taxonomic
knowledge is represented by intensional concept definitions which are
automatically arranged in a subsumption hierarchy (TAXON). Dynamic
cooperation of the subsystems is organized through access primitives
providing an interface to the respective reasoning services.
COLAB is a piece of research software developed at DFKI and the
University of Kaiserslautern.
COLAB involves 4 subsystems:
+ RELFUN is a logic-programming language with call-by-value
(eager), non-deterministic, non-ground functions, and
higher-order operations [Boley92b].
SHORT DESCRIPTION: Operational (interpreter in pure LISP), procedural
(SLV-resolution), fixpoint, and model-theoretic semantics [Boley92c].
Interpreter for full RELFUN; WAM emulator for fixed-arity subset.
Layered compiler system, from source-to-source transformers to
declarative classifier, to WAM-code generator [Boley90a]. Translator
to relational subset of RELFUN, henceforth to PROLOG. Accepting
freely interchangeable LISP-style and PROLOG-style syntaxes. Tracer
for valued conjunctions; interface to LISP; on-line help. Prelude
with useful relations/functions; library of declarative hypergraph
operations [Boley92a]; components for mechanical-engineering system
using declarative geometry [BoleyHanschke+91b]. Tight (WAM-level)
coupling with FORWARD.
+ TAXON is a terminological knowledge representation system extended by
concrete domains [BaaderHanschke91b,Hanschke92b].
SHORT DESCRIPTION: Comprises a T-box and an A-box formalism for
representing terminological and assertional knowledge. The T-box
provides expressive concept forming operators, in particular for
specifying role/attribute interaction. The TAXON A-box can
instantiate concepts, roles, etc. All reasoning services (e.g.,
classification, realization) are implemented by terminating, sound
and complete algorithms. A concrete domain of rational numbers with
comparison operators is tightly coupled with the abstract
terminological formalism. Can compute the domain hierarchy for
CONTAX.
+ CONTAX is a constraint system for weighted constraints over
hierarchically structured finite domains.
SHORT DESCRIPTION: The CONTAX system supports primitive
(extensional), compound (conjunctive), disjunctive and predicative
constraints. Constraint instances are connected by variables that
range over specific domains which can be plain or hierarchically
structured. Hierarchical domains can be defined in CONTAX itself or
by using the classifier of TAXON. Intervals regarded as subdomains of
integers are also supported. All constraints are given a weight (from
a discrete set ranging from 'hard' to 'soft') that is used by CONTAX
for relaxation of overspecified problems. Besides being integrated
in COLAB, there also exists a stand-alone version of CONTAX with a
programmer interface to LISP [MeyerSteinle92] that enables any
LISP-based application to use CONTAX as its own constraint-reasoning
formalism. The CONTAX system has already been used to formalize the
tool selection problem in a CIM application [Meyer92a,Meyer92b].
+ FORWARD is a logic programming language with bottom-up and top-down
evaluation of Horn clauses [HarmHinkelmann+92].
SHORT DESCRIPTION: User-specifiable division of Horn clauses for
bottom-up, top-down and bidirectional reasoning. Semi-naive
bottom-up evaluation with top-down provable premises. Generalized
Magic-Set transformation for goal-directed bottom-up reasoning,
supporting conjunctive queries and considering top-down premises. An
interpreter version is available, there is also an abstract machine,
which will be available in the near future. Simulation of forward
chaining in a backward chaining system by rule transformation.
Compilation into a WAM with special forward code area and additional
so-called retain stack for derived facts. Upside-down
meta-interpreter in RELFUN for forward chaining, partial evaluation
of the meta-interpreter. Tight coupling with the RELFUN system on
interpreter-level and WAM-level. A tight integration of the
semi-naive strategy with the TAXON system is currently under
development.
Other subsystems used in COLAB include
- GAMA (General Abstract Machine Assembler)
- NyWAM (WAM emulator in Common Lisp)
Requires: Common Lisp (all), CLOS (CONTAX)
Ports: RELFUN tested in AKCL, Lucid CL, Allegro CL, and
Symbolics CL. TAXON in AKCL, Lucid CL, and Symbolics CL.
CONTAX in Symbolic CL and Lucid CL. FORWARD in AKCL,
Lucid CL, and Symbolics CL.
Copying: Copyright (c) 1985-1992 by Harold Boley. (COLAB, RELFUN)
Copyright (c) 1992 by Michael Sintek (GAMA)
Copyright (c) 1991/1992 by Michael Sintek
and Werner Stein (indexing concept and algorithms)
Copyright (c) 1992 by Michael Herfert (lisp2pro/pro2lisp)
This software is distributed for non-profit and research
purposes only.
Copyright (c) May 1989 by Sven-Olof Nystroem and Uppsala
University. (NyWAM)
Redistribution permitted but not for resale.
Copyright (c) 1986 Regents of the University of California
(Defsystem)
Use, copying, modification, and distribution permitted.
CD-ROM: Prime Time Freeware for AI, Issue 1-1
Author(s): Dr. Harold Boley (COLAB/RELFUN)
DFKI
Postfach 2080
W-6750 Kaiserslautern
Germany
Tel: +49-631-205-3459
Fax: +49-631-205-3210
Knut Hinkelmann (COLAB/FORWARD)
DFKI
Postfach 2080
67608 Kaiserslautern
Germany
Tel: +49-631-205-3467
Fax: +49-631-205-3210
Manfred Meyer (COLAB/CONTAX)
DFKI
Postfach 2080
67608 Kaiserslautern
Germany
Tel: +49-631-205-3468
Fax: +49-631-205-3210
Philipp Hanschke (COLAB/TAXON)
DFKI
Postfach 2080
67608 Kaiserslautern
Germany
Tel: +49-631-205-3460
Fax: +49-631-205-3210
Contact: Dr. Harold Boley (COLAB)
DFKI
Postfach 2080
W-6750 Kaiserslautern
Germany
Tel: +49-631-205-3459
Fax: +49-631-205-3210
Contact the principle developer of each subsystem for
matters concerning that system. Requests for the entire
system should be directed to Harold Boley.
Keywords:
Assertional Knowledge, Authors!Boley, Authors!Hanschke,
Authors!Hinkelmann, Authors!Meyer, Backward Chaining, COLAB,
CONTAX, Constraint Nets, Constraint Systems, FORWARD,
Finite Domains, Forward Chaining, GAMA, GWAM, Horn Clauses,
Intensional, Knowledge Compilation, Knowledge Representation,
Lisp!Code, Logic Programming, NyWAM, RELFUN,
Subsumption Hierarchy, TAXON, Taxonomic Knowledge,
Terminological Knowledge Representation, WAM
References:
Franz Baader and Philipp Hanschke, "A Scheme for Integrating Concrete
Domains into Concept Languages", in Proceedings of the 12th
International Joint Conference on Artificial Intelligence, 1991.
Franz Baader and Philipp Hanschke, "Extensions of Concept Languages
for a Mechanical Engineering Application", in GWAI92, 1992.
H. Boley, P. Hanschke, K. Hinkelmann, and M. Meyer, "COLAB: A Hybrid
Knowledge Compilation Laboratory", Presented at 3rd International
Workshop on Data, Expert Knowledge and Decisions: Using Knowledge to
Transform Data into Information for Decision Support, Reisensburg,
Germany, DFKI GmbH, September 1991.
Harold Boley, "A Relational/Functional Language and Its Compilation
into the WAM", Universit{\"a}t Kaiserslautern, Fachbereich
Informatik, SEKI Report SR-90-05, April 1990.
Harold Boley, "Declarative Operations on Nets", Research Report
RR-90-12, DFKI GmbH, Postfach 20 80, D-6750 Kaiserslautern, October
1990.
Harold Boley, "Declarative Operations on Nets", in Fritz Lehmann,
editor, Semantic Networks in Artificial Intelligence,
23(6-9):601-637, Special Issue of Computers \& Mathematics with
Applications, Pergamon Press, 1992.
Harold Boley, "A Direct Semantic Characterization of RELFUN", in
Evelina Lamma and Paola Mello, editors, Preprints of the Proceedings
of the 3rd International Workshop on Extensions of Logic Programming,
Facolt\`a di Ingegneria, Universit\`a di Bologna, Italy, 1992.
Harold Boley, "Extended Logic-plus-Functional Programming", in
Lars-Henrik Eriksson, Lars Halln{\"a}s, and Peter Schroeder-Heister,
editors, Proceedings of the Workshop on Extensions of Logic
Programming, ELP '91 (Stockholm 1991), Springer Verlag, 1992.
Philipp Hanschke and Knut Hinkelmann, "Combining Terminological and
Rule-based Reasoning for Abstraction Processes", in GWAI-92,
Springer-Verlag, 1992.
Philipp Hanschke and Manfred Meyer, "An Alternative to
$\Theta$-Subsumption Based on Terminological Reasoning", in Celine
Rouveirol, editor, Workshop on Logical Approaches to Machine
Learning, ECAI 92, Vienna, August 1992.
Philipp Hanschke, "Specifying Role Interaction in Concept Languages",
in Third International Conference on Principles of Knowledge
Representation and Reasoning (KR '92), October 1992.
Philipp Hanschke, "Terminological Reasoning and Partial Inductive
Definitions", in Lars-Henrik Eriksson, Lars Halln{\"a}s, and Peter
Schroeder-Heister, editors, Workshop on Extensions to Logic
Programming, (Stockholm 1991), Springer-Verlag, 1992.
Martin Harm, Knut Hinkelmann, and Thomas Labisch, "Integrating
Bottom-up and Top-down Reasoning in COLAB", DFKI GmbH, Tech Report
Document D-92-27, 1992.
H.-G. Hein and M. Meyer, "A WAM Compilation Scheme", in A. Voronkov,
editor, Logic Programming: Proceedings of the $1^{st}$ and $2^{nd}$
Russian Conferences, Lecture Notes in Artificial Intelligence (LNAI)
#592, pages 201-214, Springer-Verlag, Berlin, Heidelberg, 1992.
Knut Hinkelmann, "Bidirectional Reasoning of Horn Clause Programs:
Transformation and Compilation", DFKI GmbH, DFKI Technical Memo
TM-91-02, January 1991.
Knut Hinkelmann, "Forward Logic Evaluation: Compiling a Partially
Evaluated Meta-interpreter into the WAM", in Proceedings German
Workshop on Artificial Intelligence, GWAI-92, Springer-Verlag,
September 1992.
Manfred Meyer, "Using Hierarchical Constraint Satisfaction for
Lathe-Tool Selection in a CIM Environment", in Fifth International
Symposium on Artificial Intelligence (ISAI), Cancun, Mexico December
1992.
Manfred Meyer, "Hierarchical Constraint Satisfaction and its
Application in Computer-Aided Production Planning", in Expert Systems
92, Cambridge, U.K., December 1992.
M. Meyer, H.-G. Hein, and J. M\"{u}ller}, "FIDO: Finite Domain
Consistency Techniques in Logic Programming", in A. Voronkov, editor,
Logic Programming: Proceedings of the $1^{st}$ and $2^{nd}$ Russian
Conferences, Springer-Verlag, Berlin, Heidelberg, Lecture Notes in
Artificial Intelligence (LNAI) #592, pages 294-301, 1992.
Last Web update on Mon Feb 13 10:23:52 1995
AI.Repository@cs.cmu.edu