Subject: From: AIList Moderator Kenneth Laws <AIList-REQUEST%sri-ai.arpa@CSNET-RELAY>

From: [email-masked]
Date: Wed, 18 Dec 85 01:23:06 est

Received: from sri-ai.arpa by CSNET-RELAY.ARPA id a005254; 14 Nov 85 23:37 EST
Date: Thu 14 Nov 1985 19:27-PST
Reply-to: AIList%sri-ai.arpa@CSNET-RELAY
US-Mail: SRI Int., 333 Ravenswood Ave., Menlo Park, CA  94025
Phone: (415) 859-6467
Subject: AIList Digest   V3 #169
To: AIList%sri-ai.arpa@CSNET-RELAY
Received: from rand-relay by vpi; Fri, 15 Nov 85 03:32 EST

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 <[email-masked]>
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: [email-masked]
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 <[email-masked]>
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" <[email-masked]>
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: [email-masked]
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: [email-masked]
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" <[email-masked]>
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
********************