AIList-REQUEST@SRI-AI.ARPA (AIList Moderator Kenneth Laws) (11/15/85)
AIList Digest Friday, 15 Nov 1985 Volume 3 : Issue 169
Today's Topics:
Seminars - Question-Answering Systems (UPenn) &
Bill, the Othello Program (CMU) &
Information-Based Complexity (CSLI) &
Multilisp (MIT) &
Gazing in Theorem Proving (MCC) &
Deductive Design Synthesis (SRI) &
Probabilistic Propositional Logic (Buffalo)
----------------------------------------------------------------------
Date: Mon, 11 Nov 85 16:04 EST
From: Tim Finin <Tim%upenn.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - Question-Answering Systems (UPenn)
Forwarded From: Bonnie Webber <Bonnie@UPenn> on Mon 11 Nov 1985 at 10:42
Subj: Seminar in Natural Language Processing
CIS679 - SEMINAR IN NATURAL LANGUAGE PROCESSING
SPRING 1986
The topic for this term is question-answering systems, with particular
attention to the type of information included in response to a question,
instead of or in addition to an answer. We will look at the role of plan
recognition and planning in formulating cooperative responses, as well as
considering how to circumscribe the reasoning expected of a respondent.
Response components of particular interest will be information intended to
explain or justify answers, information intended to point out and/or correct
misconceptions, and information intended to further the questioner's goals.
Instructors: Joshi/Webber
Time: MW 3-4:30
------------------------------
Date: 13 Nov 85 12:54:10 EST
From: Kai-Fu.Lee@SPEECH2.CS.CMU.EDU
Subject: Seminar - Bill, the Othello Program (CMU)
BILL :
THE OTHELLO PROGRAM
THAT BEAT IAGO
Kai-Fu Lee
Friday
November 15, 1985
Wean Hall 5409
4:30 PM - 6:00 PM
BILL is an Othello program written by myself and
Sanjoy Mahajan. It was entered in the Waterloo Othello
Tournament on November 9, and captured first place with a
4-0 record. In two unofficial games, it defeated IAGO, the
world champion othello program developed at CMU in 1980-2.
Most, if not all, othello programs use one of two
types of evaluation functions: (1) knowledge-intensive but
slow (such as IAGO), or (2) knowledge-deficient but fast
(such as most programs at Waterloo). BILL succeeds through
its use of a knowledge-intensive, yet extremely efficient
evaluation function. It is further enhanced by an
iterative deepening zero-window alpha-beta procedure, a
hash table, a linked-move killer table, a two-phase
end-game search, and thinking on opponent's time.
In this talk, I will first discuss othello strategies.
Next, I will describe Bill, and analyze its games in
Waterloo and against IAGO. Finally, we will demonstrate
BILL by playing it against the audience.
------------------------------
Date: Wed 13 Nov 85 17:05:26-PST
From: Emma Pease <Emma@SU-CSLI.ARPA>
Subject: Seminar - Information-Based Complexity (CSLI)
[Excerpted from the CSLI Newsletter by Laws@SRI-AI.]
An Introduction to Information-based Complexity
J. F. Traub
Computer Science Department, Columbia University
THURSDAY, November 21, 1985
4:15 p.m. CSLI Colloquium, Redwood Hall, Room G-19
In information-based complexity ``information'' is, informally,
what we know about a problem which we wish to solve.
The goal of information-based complexity is to create a general
theory about problems with partial and contaminated information and to
apply the results to solving specific problems in varied disciplines.
Problems with partial and contaminated information occur in areas such
as vision, medical imaging, prediction, geophysical exploration,
signal processing, control, and scientific and engineering
calculation.
For problems with partial and contaminated information, very general
results can be obtained at the ``information level.'' Among the
general results to be discussed is the power of parallel
(non-adaptive) information and the application of such information to
the solution of problems on distributed systems.
The methodology and results of information-based complexity will be
contrasted with the study of NP-complete problems where the
information is assumed to be complete, exact, and free.
------------------------------
Date: Tue 12 Nov 85 12:45:02-EST
From: "Brian C. Williams" <WILLIAMS%MIT-OZ@MIT-MC.ARPA>
Subject: Seminar - Multilisp (MIT)
Thursday , October 14 4:00pm Room: NE43- 8th floor Playroom
The Artificial Intelligence Lab
Revolving Seminar Series
"Multilisp: A Language for Parallel Symbolic Computing"
Burt Halstead
MIT, LCS
Multilisp is an extension of Scheme with additional operators and
additional semantics for parallel execution. These have been added without
removing side effects from the language. The principal parallelism
construct in Multilisp is the "future," which exhibits some features of
both eager and lazy evaluation. Current work focuses on making Multilisp a
more humane programming environment, and on expanding the power of
Multilisp to express task scheduling policies.
A skeletal Multilisp has been implemented, and has been run on the
shared-memory Concert multiprocessor, using as many as eight processors, as
well as on a BBN Butterfly machine with as many as 128 processors. The
implementation uses interesting techniques for task scheduling and garbage
collection. The task scheduler helps control excessive resource
utilization by means of an unfair scheduling policy; the garbage collector
uses a multiprocessor algorithm modeled after the incremental garbage
collector of Baker.
The talk will describe Multilisp, discuss the areas of current activity,
and indicate the future direction of the project.
------------------------------
Date: Mon 11 Nov 85 15:55:02-CST
From: AI.HASSAN@MCC.ARPA
Subject: Seminar - Gazing in Theorem Proving (MCC)
GAZING: USING THE STRUCTURE
OF THE THEORY IN THEOREM PROVING
Dave Plummer
Department of Mathematics
University of Texas at Austin
Wednesday, November 20
10:00 a.m.
Echelon I, Room 409
A mechanical theorem prover embodies two types of knowledge: logical
and non-logical. The logical knowledge informs the prover which
inferences are legal within the logic. The non-logical information,
however, is specific to the theory that the prover is working in and
includes definitions of concepts used in the theory, axioms, and
previously proved facts. The theory is structured by relationships
between these facts and these relationships may be exploited in order
to provide guidance for a mechanical theorem prover.
In this talk I will describe a technique, called Gazing, which
exploits the structure of a theory, thus aiding a mechanical prover in
determining which items of knowledge will be useful in the proof of a
given goal. As concepts are defined in the theory, the system builds
a graph representing the definitional order. This graph is used in
two ways. First, whenever a new fact enters the theory, the ordering
is used to determine an orientation of that fact creating a new
rewrite rule. Secondly, the ordering is used to guide the search for
a proof of a conjecture whenever the proof is known to require the use
of non-logical facts. This guidance takes the form of determining
which concepts are "close" in the definitional ordering, and
attempting to find rewrite rules which may be used to rewrite two
different concepts to a common new concept. The ordering can also be
used to decide which of a number of possible common rewritings is
preferable, and indeed if any common rewriting exists.
------------------------------
Date: Thu 14 Nov 85 14:31:42-PST
From: LANSKY@SRI-AI.ARPA
Subject: Seminar - Deductive Design Synthesis (SRI)
EXPLOITATION OF CONSTRAINTS IN DEDUCTIVE DESIGN SYNTHESIS
Jeff Finger
Stanford University
JFinger@SU-SUSHI
PLANLUNCH
11:00 AM, MONDAY, November 18
SRI International, Building E, Room EJ228 (new conference room)
The talk will cover two related topics in deductive design synthesis:
(1) efficiency gained by reasoning forward from subgoals, and
(2) advantages and disadvantages of using a declarative representation
for partially completed designs.
The first part of the talk gives the deductive framework for capturing the
following intuition:
Suppose I have decided that X and Y and to be true of my
design. Perhaps I should think about what else X and Y imply
about the design, say Z. Otherwise, I might waste time
trying to complete the design process by making decisions
that have *already* been ruled out by X and Y, for example,
NOT(Z).
The conditions that X and Y imply (called "necessary constraints" or "NC's")
are found via reasoning forward from subgoals. We show how NC's of a
subgoal can be used to prune the design space either by preventing some
impossible possibilities from ever being generated or by providing a quick
means of filtering bad choices. In terms of resolution, the above use of
NC's corresponds to the rather counterintuitive notion of allowing
OR-INTRODUCTION on clauses in the set of support. We will also discuss
inheritance of NC's from goal to subgoal and the relation of finding NC's to
that of checking consistency of partially completed designs.
The second part of the talk deals with declarative representation of
partially completed designs. Deductive design systems such as QA3 or Manna
and Waldinger's reify the design as a single term in the logic.
However, it is difficult to express many sorts of constraints on partially
completed designs as a single term. Examples include two actions in an
unspecified order, or the constraint that Action A takes place less than 3
seconds or more than 8 seconds after Action B. We present a system called
RESIDUE in which we build up the design as a set of facts we are willing to
assume about of the design. Using facts rather than a single term, we can
make finer-grained decisions, avoiding unwitting commitments that might
result in unnecessary backtracking. In addition, forward reasoning on
subgoals (as in the first portion of the talk) may be done directly on the
set of facts.
------------------------------
Date: Thu, 14 Nov 85 10:40:19 EST
From: "William J. Rapaport" <rapaport%buffalo.csnet@CSNET-RELAY.ARPA>
Subject: Seminar - Probabilistic Propositional Logic (Buffalo)
UNIVERSITY AT BUFFALO
STATE UNIVERSITY OF NEW YORK
DEPARTMENT OF COMPUTER SCIENCE
COLLOQUIUM
DEXTER KOZEN
Department of Computer Science
Cornell University
A PROBABILISTIC PROPOSITIONAL DYNAMIC LOGIC
This talk concerns a probabilistic analog of Propositional
Dynamic Logic, called Probabilistic Propositional Dynamic Logic
(PPDL). PPDL is useful in the formal manipulation of simple pro-
babilistic programs and the average-case analysis of determinis-
tic programs. We describe the formal syntax and semantics of the
system and its deductive calculus, and illustrate its use by cal-
culating the expected running time of a simple random walk. We
also describe briefly a polynomial-space decision procedure for
deciding the truth of formulas involving well-structured pro-
grams.
Thursday, November 21, 1985
3:30 P.M.
Bell 337, Amherst Campus
Wine and cheese will be served at 4:30 P.M., 224 Bell Hall
For further information, call (716) 636-3181.
William J. Rapaport
Assistant Professor
Dept. of Computer Science, SUNY Buffalo, Buffalo, NY 14260
(716) 636-3193, 3180
uucp: ...{allegra,decvax,watmath}!sunybcs!rapaport
...{cmc12,hao,harpo}!seismo!rochester!rocksvax!sunybcs!rapaport
cs: rapaport@buffalo
arpa: rapaport%buffalo@csnet-relay
bitnet: rapaport@sunybcs
------------------------------
End of AIList Digest
********************