Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!husc6!bloom-beacon!oberon!cit-vax!ucla-cs!zen!ucbvax!VENICE.AI.SRI.COM!lansky
From: lansky@VENICE.AI.SRI.COM (Amy Lansky)
Newsgroups: comp.ai.digest
Subject: Seminar - Non-Deterministic Lisp (SRI)
Message-ID: <8710141854.AA07312@venice>
Date: Wed, 14-Oct-87 14:54:41 EDT
Article-I.D.: venice.8710141854.AA07312
Posted: Wed Oct 14 14:54:41 1987
Date-Received: Sat, 17-Oct-87 17:37:24 EDT
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 28
Approved: ailist@kl.sri.com


      DEPENDENCY-DIRECTED BACKTRACKING IN NON-DETERMINISTIC LISP

                Ramin Zabih  (RDZ@SUSHI.STANFORD.EDU)
                     Computer Science Department
                         Stanford University

                   11:00 AM, MONDAY, October 19
              SRI International, Building E, Room EJ228

Dependency-directed backtracking is a strategy for solving
generate-and-test search problems.  Pure Lisp extended with McCarthy's
non-deterministic operator AMB is an elegant language for expressing
such problems.  I will describe how to automatically provide
dependency-directed backtracking in SCHEMER, a non-deterministic Lisp
dialect.

It is also possible for SCHEMER to automatically provide other search
strategies than dependency-directed backtracking.  In fact, SCHEMER
can support a large class of solution methods.  I will show that
SCHEMER programs can make use of any algorithm for determining the
satisfiability of a propositional formula in Conjunctive Normal Form.

This is joint work with David McAllester.


VISITORS:  Please arrive 5 minutes early so that you can be escorted up
from the E-building receptionist's desk.  Thanks!