THE LazyRMS: AVOIDING WORK IN THE ATMS

The basic algorithms involved in reason maintenance in the standard ATMS is known to have a computational complexity that is exponential in the worst case. Yet, also in average-case problem solving, the ATMS often lays claim to a major part of the computational effort spent by a problem solver/ATMS system. In this paper, we argue that within the limits of the worst-case computational complexity, it is possible to improve on the average-case complexity of reason maintenance and query processing by eliminating computation that is of no relevance to the problem solver's performance. To this purpose, we present a set of algorithms designed to control the effort spent by the ATMS on label updating. The basic idea underlying these algorithms is that of lazy evaluation: labels are not automatically maintained on all datums but are computed only when needed (either directly or indirectly) by the problem solver. The algorithms have been implemented in the LazyRMS with which we have experimented in the context of model-based diagnosis; our experiments show a substantial saving in the computational effort spent on reason maintenance.