Ernest Schimmerling

Mathematical logic seminar - February 26, 2003

Speaker:		John Hooker T. Jerome Holleran Professor of Business Ethics and Social Responsibility Director, Center for International Corporate Responsibility Graduate School of Industrial Administration Carnegie Mellon University
Title:		Resolution-based dynamical search
Abstract:

This talk presents a family of search methods that combine the completeness of branching with some of the flexibility of local search. Completeness is achieved by applying a limited form of resolution to the set of nogoods so far generated. Stronger forms of resolution allow greater freedom but incur more overhead. At one extreme, full resolution allows complete freedom, and at the other, chronological backtracking is inflexible but uses a very fast form of resolution. This family of methods generalizes backjumping, dependency-directed backtracking, dynamic backtracking, and the partial order dynamic backtracking of Ginsberg and McAllester. The ideas are presented through a series of examples.