AIList-REQUEST@SRI-AI.ARPA (AIList Moderator Kenneth Laws) (12/10/85)
AIList Digest Tuesday, 10 Dec 1985 Volume 3 : Issue 183
Today's Topics:
Seminars - CAKE Knowledge Representation and Reasoning System (MIT) &
- SOJA Scheduling System (CMU) &
- Fault Analysis using Dynamic Behavior (Rutgers) &
- Toward a Theory of Algorithm Improvement (Oregon State) &
- Inheritance, Data Models and Data Types (MIT) &
- STRIPS and Circumscription (SU) &
- Semi-Applicative Programming (SRI) &
- Connectionist Talk Talk (SU) &
- Possible Worlds and Situations Semantics (UPenn)
----------------------------------------------------------------------
Date: Mon, 2 Dec 85 09:22 EST
From: Brian C. Williams <WILLIAMS@OZ.AI.MIT.EDU>
Subject: Seminar - CAKE Knowledge Representation and Reasoning System (MIT)
[Forwarded from the MIT bboard by SASW@MIT-MC.]
Thursday , December 5 4:00pm Room: NE43- 8th floor Playroom
The Artificial Intelligence Lab
Revolving Seminar Series
CAKE:
An Example of a Hybrid Knowledge Representation
and Reasoning System
Charles Rich
MIT AI Lab
Cake is a knowledge representation and reasoning system being developed
to support automated programming (the Programmer's Apprentice). The
first part of this talk describes the architecture of Cake, which is
divided into the following nine layers, each with associated
representations and reasoning procedures:
Plan Synthesis
Plan Recognition
Plan Calculus
Frames
Types
Algebraic
Demons
Equality
Truth Maintenance
The second part of the talk takes a look at some of the issues in the
design of hybrid systems generally, such as
What is a hybrid system?
Why would you want one?
Who is developing them?
Where do we go from here?
Nelson & Oppen's cooperating decision procedures, KL-Two, Krypton, and
Cake will be discussed as examples of hybrid systems.
------------------------------
Date: 4 Dec 85 11:30:50 EST
From: Jeanne.Bennardo@ISL1.RI.CMU.EDU
Subject: Seminar - SOJA Scheduling System (CMU)
Intelligent Systems Lab Seminar
Topic: Presentation of SOJA project.
Speaker: Claude Le Pape
Place: DH3313
Date: Friday, Dec. 6
Time: 10:30am - 11:30am
Speaker:
Claude Le Pape is a visiting researcher from the Laboratoires de Marcoussis
in France, and is currently working in the Intelligent Systems Lab with the
Phoenix/Opis project.
Abstract:
We have implemented in the Laboratoires de Marcoussis - in Franz Lisp -
a daily scheduling system called SOJA. Given the state of the shop in the
evening, SOJA builds a scheduling plan for the next day. This implies :
- selecting the operations to be performed over the day
- scheduling them and computing a time-table for each machine.
Two planning steps are distinguished in SOJA : Selection and Scheduling.
- Selection is done according to the state of the shop and the orders to
be completed. Selection rules are used to build a tagged graph,
which nodes are phases (operations). Each arc is tagged according to a
reason for selecting its extremity, and valued in order to measure the
significance of this reason. Then SOJA examines this graph and the
resource requirements to decide which phases should be scheduled.
- Scheduling is considered as a constraint-directed reasoning task.
However, preferences are not represented as constraints, but as scheduling
rules that are used to make decisions.
Both selection and scheduling processes use an inference engine that has
been specially designed for SOJA. We will describe this engine and the
solutions we have implemented to make it efficient :
- combination of forward and backward chaining
- preservation of partial instances of rules (and propagation)
- compilation of rules.
We will also discuss our constraint representation and backtracking.
A short comparison between SOJA and ISIS is also scheduled.
------------------------------
Date: 4 Dec 85 10:38:59 EST
From: Smadar <KEDAR-CABELLI@RED.RUTGERS.EDU>
Subject: Seminar - Fault Analysis using Dynamic Behavior (Rutgers)
III Seminar
Title: Using Dynamic Behavior of Physical Systems for Fault Diagnosis
Speaker: Kathy Abbott
Date: Thursday, December 5, 1985, 11:30-12:30PM
(*** notice date and time change ***)
Place: Hill Center, room 423
Kathy Abbott, a Ph.D. candidate in our department and
researcher at NASA - Langley, will discuss her dissertation research
on fault diagnosis. Here is her abstract:
One consideration when performing real-time diagnosis of
physical systems is that the system's behavior may change as time
progresses. The effect of a failure may propagate through the system
under consideration as well as to systems either functionally or
physically adjacent to it. This dynamic behavior can be used to prune
fault hypotheses by using models of the physical system to identify
how the fault is propagating, the type of fault, and what components
of the physical system are affected. An advantage of using functional
and physical models in this manner is that it permits reasoning about
incomplete information, such as, lack of measurements due to physical
damage, system parameters that are not sensed, or sampling times that
are not frequent enough to detect all system changes.
In this talk I will discuss a model-based diagnosis system
which uses the dynamic behavior of physical systems in the diagnosis
process. The diagnosis system is not yet completely fleshed out in
all details, so any constructive comments or suggestions are
particularly welcome at this time.
------------------------------
Date: Thu, 5 Dec 85 14:00:35 pst
From: Tom Dietterich <tgd%oregon-state.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - Toward a Theory of Algorithm Improvement (Oregon State)
This colloquium has already happened, but I thought you might still
be interested in sending it to AILIST. --Tom
Departmental Colloquium
Oregon State University
Department of Computer Science
Wednesday, Nov. 20, 1985
TOWARD A THEORY OF ALGORITHM IMPROVEMENT
Thomas G. Dietterich
Department of Computer Science
Oregon State University
This talk will sketch a theory of algorithm improvement called the "test
incorporation" theory. The basic premise of test incorporation theory is
that all algorithms can be usefully viewed as improvements of a naive
generate-and-test algorithm. The improvements can take one of two forms:
(a) movement along the space-versus-time tradeoff curve and (b)
INCORPORATION of test information into the generator of possible solutions.
Examples will be presented for each kind of performance improvement. The
talk will then take up the questions of WHEN these improvements take place
and WHAT PROGRAM is performing the improvements. Traditional compilers
perform simple kinds of improvements at "compile-time". However, many more
powerful algorithms make these improvements to themselves dynamically at run
time, particularly when new input data is made available.
Test incorporation theory can be employed in two ways: (a) to analyze
existing programs and understand why they are successful, and (b) to design
new programs. The test incorporation perspective also provides some
interesting answers to the questions "What is computer science?" "What is
knowledge?" and "What is intelligence?"
This work is a joint project with James Bennett of Teknowledge, Inc.
------------------------------
Date: Thu, 5 Dec 85 16:21:29 est
From: nikhil at MIT-NEWTOWNE-VARIETY.MIT.EDU (Rishiyur S. Nikhil)
Subject: Seminar - Inheritance, Data Models and Data Types (MIT)
[Forwarded from the MIT bboard by SASW@MIT-MC.]
Inheritance, Data Models and Data Types
Peter Buneman
University of Pennsylvania
The notion of type inheritance (subsumption, ISA hierarchies) has long been
recognised as central to the development of programming languages, databases
and semantic networks. Recent work on the semantics of programming languages
has shown that inheritance can be cleanly combined with functional
programming and can itself serve as a model for computation.
Using a definition of partial functions that are well behaved with respect to
inheritance, I have been investigating a new characterization of the
relational and functional data models. In particular, I want to show the
connections of relational database theory with type inheritance and show how
both the relational and functional data models may be better integrated with
typed programming languages.
Host: Prof. Rishiyur Nikhil
Date: Friday, December 6, 1985
Time: 2:00 pm - Refreshments
2:15 pm - Lecture
Place: Room NE43-512A
MIT Laboratory for Computer Science,
545 Technology Square,
Cambridge, MA 02139
------------------------------
Date: 05 Dec 85 1134 PST
From: Vladimir Lifschitz <VAL@SU-AI.ARPA>
Subject: Seminar - STRIPS and Circumscription (SU)
STRIPS and Circumscription:
Two Approaches to the Frame Problem
Vladimir Lifschitz
Wednesday, December 11, 2:00
MJH 252
The frame problem consists in defining which properties of
situations do not change across events. We will compare two well-known
attempts to solve the frame problem. One, the STRIPS approach, is
based on using a language which has no explicit references to
situations. The other approach uses circumscription to express the
"commonsense law of inertia", according to which the differences
between two situations separated by an event are minimal, given the
properties of the event. We will show on a simple example how to
transform a circumscriptive theory into the description of the
corresponding STRIPS operator.
------------------------------
Date: Fri 6 Dec 85 15:05:51-PST
From: Phil Cohen <PCOHEN@SRI-AI.ARPA>
Subject: Seminar - Semi-Applicative Programming (SRI)
N. S. Sridharan, of BBN Labs, will give a seminar next Tues, the 10th,
10:30 am, in EJ228. Title and abstract below.
Title: Semi-applicative Programming
Most current parallel programming languages are designed
with a sequential programming language as the base language and have
added constructs that allow parallel execution. We are experimenting
with an applicative base language that has implicit parallelism
everywhere, and then we introduce constructs that inhibit parallelism.
The base language uses pure LISP as a foundation and blends in
interesting features of Prolog and FP. Proper utilization of
available machine resources is a crucial concern of programmers. We
advocate several techniques of controlling the behavior of functional
programs without changing their meaning or functionality: program
annotation with constructs that have benign side-effects, program
transformation and adaptive scheduling. This combination yields us a
SEMI-APPLICATIVE programming language and an interesting programming
methodology.
Starting with the specification of a context-free recognizer, we have
been successful in deriving variants of the recognition algorithm of
Cocke-Kasami-Younger. One version is the CKY algorithm in parallel.
The second version includes a top-down predictor to limit the work
done by the bottom-up recognizer. The third version uses a cost
measure over derivations and produces minimal cost parses using a
dynamic programming technique. In another line of development, we
arrive at a parallel version of the Earley algorithm.
------------------------------
Date: Fri, 6 Dec 85 06:03:17 pst
From: gluck@SU-PSYCH (Mark Gluck)
Subject: Seminar - Connectionist Talk Talk (SU)
NETTALK: Teaching a Massively-Parallel Network to Talk
Dec. 18th, 1:00 pm, at Redwood hall
Terrence J. Sejnowski
Biophysics Department
Johns Hopkins University
Baltimore, MD 21218
ABSTRACT
Text to speech is a difficult problem for rule-based systems
because English pronunciation is highly context dependent and there are
many exceptions to phonological rules. An alternative knowledge
representation for correspondences between letters and phonemes will be
described in which rules and exceptions are treated uniformly and can
be determined with a learning algorithm in a connectionist model. The
architecture is a layered network of 400 simple processing units with
9,000 weights on the connections between the units. The training
corpus is continuous informal speech transcribed from tape recordings.
Following training on 1000 words from this corpus the network can
generalize to novel text. Even though this network was not designed to
mimic human learning, the development of the network in some respects
resembles the early stages in human language acquisition. Following
damage of the network by either removal of units or addition of random
values to the weights the performance of the network degraded
gracefully. Issues which will be addressed include scaling of the
learning algorithm with the size of the problem, robustness of
learning to predicate order of the problem, and universality of
learning in connectionist models.
------------------------------
Date: Mon, 9 Dec 85 11:58 EST
From: Tim Finin <Tim%upenn.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - Possible Worlds and Situations Semantics (UPenn)
Forwarded From: Dale Miller <Dale@UPenn> on Mon 9 Dec 1985 at 8:58
Joint Mathematics / Computer Science
LOGIC COLLOQUIUM
Possible Worlds and Situations Semantics
Greg Hager
CIS Department, UPenn
Monday 9 December 1985
4:40 pm, DRL 4E17
Situation theory is an attempt by its developers (philosopher John Perry and
mathematician Jon Barwise) to provide an alternative framework for the study
of language and meaning. Their approach has been to start over from first
principles and construct a theory which does not rely on classical logic as
developed by Frege -- in particular emphasizing the notions of partial
information, a relational theory of meaning, and mathematical realism.
Needless to say this has provoked substantial interest, debate, and
skepticism from a variety of sources.
Any complete understanding of pros and cons of this theory requires a
substantial knowledge of philosophy, mathematics, and linguistics (none of
which I can lay claim too). However, from one point of view, situation
theory can be loosely construed as an alternative to possible worlds theory
and its application to the study of language by Montague. In this talk, I
will focus on the development of possible worlds semantics and its use in
linguistics, and point out where situation theory diverges or disagrees.
This discussion will be fairly general and open-ended, so audience
participation is welcomed and encouraged.
------------------------------
End of AIList Digest
********************