leff@smu.UUCP (Laurence Leff) (03/27/89)
Forschungsberichte Kuenstliche Intelligenz
Institut fuer Informatik
Technische Universitaet Muenchen
Arcisstr. 21
D-8000 Muenchen 2
Telex: tumue d 05-22854
Fax: +49 - 89 - 2800529
e-mail: fki@lan.informatik.tu-muenchen.dpb.de
fki@tumult.uucp
The following papers can be obtained free of charge at the address given above.
Requests to: Angela Marquardt code "FKI".
FKI-84-88
Cognitive Science -- Eine Standortbestimmung
(in German)
Christian Freksa
Abstract:
The paper sketches the formation of the field `Cognitive Science` in the 1970s
as an umbrella discipline for aspects of psychology, linguistcs, artificial
intelligence, anthropology, philosophy, and the neurosciences. The example of
color naming is used to demonstrate the interdisciplinary approach to
cognition. The AI phenomenon is considered from a cognitive point of view.
Important topics and the first results of Cognitive Science and the
contributions of the subdisciplines are summarized.
FKI-85-88
Intrinsische vs. extrinsische Repraesentation zum Aufgabenloesen
oder die Verwandlung von Wasser in Wein
(in German)
Christian Freksa
Abstract:
Real world problem solving is presented as a task that can be performed
either by an action in the real world or by formalization, inference,
interpretation in an artificial world. The paper focuses on the difficulty
of constructing adequate formalizations of real world problems. Properties
of relations and their intrinsic and extrinsic representation are discussed.
The distinction between "simulation" and "explanation" of real world
behavior is drawn. The formalization problem is exemplified by a human
approach to the "wine mixing problem".
FKI-86-88
FHCL - Functions in Horn Clause Logic
Furbach U., Hoelldobler S.
Abstract:
We propose a general scheme for the combination of functional and logic
programming. This scheme is based on an extended unification algorithm, where
expressions are evaluated functionally before an attempt is made to unify them
syntactically. Whenever syntactic unification is not possible we apply
well-known techniques for solving sets of equations under the theory defined by
the functional program instead of reporting a failure. The correctness of the
scheme is proved wih respect to these techniques. We present an implementation
of FHCL and its application to a sophisticated programming task: the derivation
of smoothsort. Finally, we outline a parallel version of FHCL which is running
on a multi-processor architecture.
FKI-87-88
Transformation Systems for Program Synthesis:
Knuth-Bendix Completion and Fold/Unfold
Bertram Fronhoefer, Ulrich Furbach
Abstract:
This paper is a comparative study in program synthesis. Two
approaches - program synthesis by means of the Knuth-Bendix
completion procedure (KBCP) and a classical transformation
system based on the unfold/fold technique - are examined.
A farreaching conformity is detected in the two systems while
on the other hand disparities in the derivations of programs
reveal principal restrictions to a straightforward translation of
derivations from one system into the other.
FKI-88-88
Module Fault Localization in a Software Toolbus based System
Daniel Hernandez
Abstract:
We incorporate a fault localization capability into POLYLITH (Purtilo 86),
a system that supports the interconnection of heterogenous software modules.
To this end we apply techniques developed in the context of diagnosis of
technical systems.
These techniques are based on explicit descriptions of the structure and
behavior of the system to be diagnosed.
The POLYLITH Module Interconnection Language (MIL) originally provides a
description of software interconnectivity (structure), which is enhanced
here by attributes specifying the high level behavior of the modules.
Furthermore, the run-time support by the POLYLITH software bus gives us
access to the actual behavior of the system under consideration.
Given enough information we are then able to determine a module or set of
modules that must be faulty in order to explain the given observations.
The MOFALO system (implemented in Franz Lisp on a Sun Workstation)
consists of a modified syntax for the POLYLITH MIL together with routines
translating it into the object-oriented internal representation, some
``algebras'' or behavior description languages for the example domains,
and the core fault localization algorithm, which is based on (deKleer,
Williams 87).
FKI-89-88
Sorts are Nothing but Functions.
An Equational Approach to Sorts for Logic Programming
Thierry Conrad, Ulrich Furbach
Abstract:
We propose a look at many-sorted logic programming as an immediate application
of equational logic programming. Definition of sorts as well as specification of
operations and orderings on them is made by means of rewriting rules. Such a
rewriting system can be associated with any Prolog program by the usual methods
of equational logic programming. The operational semantics of an extended
program is based on a resolution procedure using equational unification. Some
examples of applications are proposed.
FKI-90-88
Logic oriented Program Synthesis
Christoph Kreitz, Gerd Neugebauer
Abstract:
Automated Program Synthesis from logical specifications nowadays has to face
attacks coming from two directions. "Real" Programmers often argue that it is a
nice academic toy, good to generate a handful of small examples, but of no use
at all in the hard real world of software technology. On the other hand, due to
the advent of Logic Programming the distinction between specification language
and program language got blurred and some people believe that Program Synthesis
has become an obsolete field of research. In view of the existing papers and
systems both opinions appear to be quite natural. Therefore it has to be
clarified where the real great challenges to Program Synthesis are today.
Our paper intends to open the discussion on the topic again by expounding a view
of the field which arose from experiences with implementing a Logic Oriented
Program Synthesizer (LOPS). After stating what the tasks of a Program Synthesis
System should be we will give a methodological guideline for the practical
realization of such a system. By following our suggestions, we believe, both
attacks against the field can be countered successfully. Firstly, Program
Synthesis will indeed have useful applications in industry and secondly, as we
will show, Logic Programming languages are not at all a solution to the problems
of the field.
FKI-91-88
Wissensrepraesentation in kuenstlichen symbolverarbeitenden Systemen
(in German)
Ulrich Furbach, Christian Freksa, Gerhard Dirlich
Abstract:
The report contains a chapter of a book on Cognitive Psychology. It
addresses the importance of knowledge representation issues for cognitive
psychologists. Knowledge representation is presented as a constructive
cognitive process. An example from the AI blocks world domain serves to
identify the system representing knowledge about a given part of the real
world. An example from the office automation domain serves to illustrate the
knowledge engineering task of designing knowledge based systems. Components
of a knowledge representation system are identified and an approach towards
developing a theory of knowledge representation is outlined. Finally an
overview of current issues of knowledge representation is given.
FKI-92-88
Utterance Generation Without Choice
Erwin Kloeck
Abstract:
In this paper we discuss a parallel processing model for the generation
of linguistic surface structures from a conceptual represenation of the
utterance content. We focus in particular on the verb selection task and
its integration into a system for sentence production and introduce the
notion of uttering pressure to control the moment of verbalization. The
resulting model allows for different surface realizations of a single
proposition without requiring an explicit choice among the alternatives.
The system architecture presented consists of several independent spreading
activation networks that communicate via a global blackboard. This setup
combines the advantages of a classical modular system with the processing
characteristics of the connectionist paradigm.
FKI-93-88
Loop Program Synthesis Using Array Traversing Modules
Vytautas Cyras
Abstract:
An approach to loop program synthesis is proposed.
Program synthesis using functional modules (F-modules), which perform
computations according to recurrence relations on arrays, is considered.
We propose to use a library of array traversing algorithms,
called structural modules (S-modules).
Each structural module contains a loop program, which organizes the
traversing of a particular data structure region invoking functional modules.
We propose techniques representing the semantics of F-modules, S-modules,
and of the application of S-modules to F-modules.
An algorithm for the synthesis of programs represented by nested loops is
presented.
Pattern matching techniques are proposed for program synthesis.
Examples of synthesized programs are given.
FKI-94-88
Der Netzeditor
Eine komfortable Umgebung zum Erstellen und Testen von konnektionistischen
Netzen
(in German)
Kai Zimmermann
Abstract:
As connectionist networks become more and more important in artificial
intelligence research we developed a system to support the design and testing of
such networks. The system enables the user to construct networks from several
unit and link types which are either provided by the system or defined by the
user. He can do this interactively through a convenient menu-driven interface or
network description language. The user can simulate the behavior of the networks
in a synchronous or asynchronous operation mode. He is provided with a graphical
display of the network's state and can use it to change the activation of units
during LOOPS and Interlisp-D on a Siemens-AI-Workstation. The paper describes
the built-in high-level user interface, containing command windows, menues,
editors and the network descritpion language, and gives examples how to use the
system efficiently. A special chapter explains the internals of the low-level
parts which are useful for researchers who want to build their own
applications.
FKI-95-88
Generierung natuerlichsprachlicher Saetze in unifikationsbasierten Grammatiken
(in German)
Andreas Stolcke
Abstract:
The first part of the report surveys and analyzes several impor-
tant contributions to natural language generation. We then focus
on unification-based grammars and formally define a notion of
output specification for this type of grammar.
The second part presents a connectionist approach to unification
in general and unification-based grammars in particular. It is
shown that unification is amenable to a (localist) connectionist
implementation which maximally explores parallelism while keeping
space requirements at a reasonable level (O(n^3), n the total
size of structures to be unified). The approach is then extended
to generate sentences from simple unification-based grammars,
`simple' meaning essentially that input to the generation is suf-
ficiently specific to prevent backtracking.
Keywords: natural language generation, unification, connectio-
nism.
FKI-96-88
Zur Portierbarkeit taxonomischer Wissensbasen zwischen heterogenen Systemen
(in German)
Andreas Strasser
Abstract:
This reports about a formalism to describe taxonomic
knowledge (hierachies of terms) with a set of
(Prolog-) predicates. With these predicates we are able
to describe all basic relations between objects in a declarative
manner.
It is highly important for us to be able to change such taxonomic
knowledge-bases into other knowledge-representation systems.
We show this with two examples.
It is one advantage of such a method,
that one can implement a taxonomy without determining one special
knowlege-representation system at the very beginning.
On the other hand we can use Prolog directly to execute syntactical
and semantic consistency checks.
Moreover, the knowledge engineer is not restricted by any limits which
are given by such systems.
FKI-97-88
S E T H E O : a SEquential THEOremprover for first order logic
- Version 2 -
Bayerl S., Letz R., Schumann J.
Abstract:
A sound and complete theorem prover for first order logic is presented.
It is based on the Connection Method and contains
several strategic and heuristic features. The paper
comprises the theoretical background, the modular structure
as well as details of the implementation.
FKI-98-89
Connectionist Approach to the Description of Spatial Knowledge
and related papers
W.Brauer, C. Freksa and the AI/Cognition Group
Abstract:
This Report collects five papers related to the ongoing project
"Connectionist Approaches to the Description of Spatial Knowledge". The
primary goal of this project is to study the applicability of connectionist
approaches to the task of describing spatial knowledge in a cognitively
plausible way. The particular application is a system to give directions for
going from a current location to a goal location in an urban setting. Given
the current state of the art in connectionist systems, we are not seeking a
closed "connectionist solution" but rather exploring their usefulness for the
various subtasks composing our system, like:
-representing spatial knowledge
-finding adequate paths between a start and a goal location
-generating natural language descriptions of those paths
While the first paper gives an overview of the project, the others describe
detailed work on particular aspects such as a path-finding algorithm, a
knowledge theoretic framework, the credit assignment problem in recurrent
networks and ways to improve back-propagation.
FKI-99-89
Logic and Reasoning with Neural Models
Franz Kurfess
Abstract:
In this paper, we discuss the use of neural nmodel methodologies in the domain
of logic and reasoning. We see three promising aspects in their application to
this domain: First, they can offer valuable support in the evaluation of logic
programms by automatically gathering (meta-)knowledge about the evaluation
process (proof) and their particular domain, thus preparing the successful
application of strategies and heuristics. Second, they can provide basic
building blocks (e.g. for unification) with a straitforward potential for
philosophical logic extensions (nonmonotonic, fuzzy, etc.). Third, self-
contained inference mechanism based on neural models could be the core of a new
class of reasoning systems.
The combination of logic nand reasoning with neural models looks quite favorable
due to their inherent capability of abstraction, generalization and laerning;
their highly parallel scheme of operation also might provide the conputational
power and flexibility which still is a hindrance to the use of conventional
logic-based systems. The underlying evaluation mechanism, however, has not yet
been investigated thoroughly enough to allow for reliable predictions on the
usability of neural models for reasoning and logic.