An optimal backtrack algorithm for tree-structured constraint satisfaction problems
Roberto J. Bayardo Jr. and Daniel P. Miranker
Artificial Intelligence 71 (1994) 159-181
Abstract
This paper present and evaluates an optimal backtrack algorithm for solving tree-structured contraint satisfaction-problems - a subset of constraint satisfaction problems which can be solved in linear time. Previous algorithms which solve these problems in linear time perform expensive preprocessing steps before ateempting solution. The work presented here reolved the open problem posed by Dechter (1990) on the development of an algorithm wwhihc avoids this preprocessing. We demonstrate significant improvements in average-case performance over the previous state of the art, and show the benefits provided to backtrack enhancement schemes exploiting the easiness of tree-structured problems such as the cycle-cutset method (Decther and Pearl, 1987).
full-text.pdf
A New Approach to Modularity in Rule-Based Programming
(desribes the Venus Rule Language)
James C. Browne, Allen Emerson, Mohamed G. Gouda, Daniel P. Miranker,
Aloysius Mok,
Roberto Bayardo Jr., Sarah Chodrow, David Gadbois, Furman Haddix, Thomas W.
Hetherington, Lance Obermeyer, Duu-Chung Tsou,
Chih-Kan Wang, Rwo-hsi Wang
Proceedings of the IEEE Conference on Tools for Artificial Intelligence, 1994
Abstract
In this paper we describe a purely declarative method for introducing
modularity into forward-chaining, rule-based languages and its
embodiment in the Venus rule language. The method is enforced by the
syntax of the language and includes the ability to parameterize the
rule groups. Drawing from two of three Venus applications developed to
date, we illustrate how this form of modularity contributes directly
to the resolution of certain software engineering problems associated
with rule languages.
full-text.ps