tgd@oregon-state.CSNET (Tom Dietterich) (11/11/86)
"These systems don't usually have any deductive power at all,
they are merely constraint satisfaction devices."
--David Etherington
I am confused by this last sentence. Isn't constraint satisfaction
a kind of inference? deKleer's ATMS and McAllester's RUP handle
large portions (maybe all?) of propositional logic.
--Tom Dietterich
Department of Computer Science
Oregon State University
Corvallis, OR 97331
tgd%oregon-state.csnetrggoebel%watdragon.waterloo.edu@RELAY.CS.NET (Randy Goebel LPAIG) (11/13/86)
> "These systems don't usually have any deductive power at all, > they are merely constraint satisfaction devices." > --David Etherington > > I am confused by this last sentence. Isn't constraint satisfaction > a kind of inference? deKleer's ATMS and McAllester's RUP handle > large portions (maybe all?) of propositional logic. > > --Tom Dietterich If one views constraint satisfaction as incremental model elimination, then there is a kind of inference going on, e.g., the number of models for p(X) & q(X) is reduced by adding the new constraint r(X), to get p(X) & q(X) & r(X). One can further see constraint satisfaction as inference by looking at Prolog puzzle solutions, where a list of constraints is posed as a goal, and the resolution prover must find a satisfying substitution; there is search involved, but satisfying substitutions are consequences of the axioms. Perhaps the best intuition about ``truth maintenance''-like systems is that they provide what is necessary for efficiently locating derivation steps that relied on assumptions. It's probably natural that any actual implementation blurs the distinction between the derivation maintenance and retrieval subsystem, and the prover that actually applies the inference rules to build derivations. Randy Goebel