drose@CIP.UCI.EDU (Don Rose) (09/17/86)
Does anyone know whether the standard algorithms for belief revision
(e.g. dependency-directed backtracking in TMS-like systems) are
guaranteed to halt? That is, is it possible for certain belief networks
to be arranged such that no set of mutually consistent beliefs can be found
(without outside influence)? --Donald Rose
drose@ics.uci.edu
ICS Dept
Irvine CA 92717hamscher@HT.AI.MIT.EDU (Walter Hamscher) (09/20/86)
Date: Mon, 08 Sep 86 16:48:15 -0800 From: Don Rose <drose@CIP.UCI.EDU> Does anyone know whether the standard algorithms for belief revision (e.g. dependency-directed backtracking in TMS-like systems) are guaranteed to halt? That is, is it possible for certain belief networks to be arranged such that no set of mutually consistent beliefs can be found (without outside influence)? I think these are two different questions. The answer to the second question depends less on the algorithm than on whether the underlying logic is two-valued or three-valued. The answer to the first question is that halting is only a problem when the logic is two-valued and the space of beliefs isn't fixed during belief revision [Satisifiability in the propositional calculus is decidable (though NP-complete)]. Doyle's TMS goes into infinite loops. McAllester's won't. deKleer's ATMS won't loop either, but that's because it finds all the consistent labelings, and there just might not be any. Etc, etc; depends on what you consider ``standard.'' Walter Hamscher