lansky@VENICE.AI.SRI.COM (Amy Lansky) (10/14/87)
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!