dekleer.pa@XEROX.COM (09/21/86)
Does anyone know whether the standard algorithms for belief revision
(e.g. dependency-directed backtracking in TMS-like systems) are
guaranteed to halt?
It depends on what you consider the standard algorithms and what do you
consider a guarantee? Typically a Doyle-style (NMTMS) comes in two
versions, (1) guaranteed to halt, and, (2) guaranteed to halt if there
are no "odd loops". Version (2) is always more efficient and is
commonly used. The McAllester-style (LTMS) or my style (ATMS) always
halt. I don't know if anyone has actually proved these results.
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)?
Sure, its called a contradiction. However, the issue of what to do
about odd loops remains somewhat unresolved. By odd loop I mean a node
which depends on its own disbelief an odd number of times, the most
trivial example being give A a non-monotonic justification with an empty
inlist and an outlist of (A).