Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rutgers!sri-spam!ames!ucbcad!ucbvax!RELAY.CS.NET!rggoebel%watdragon.waterloo.edu
From: rggoebel%watdragon.waterloo.edu@RELAY.CS.NET (Randy Goebel LPAIG)
Newsgroups: mod.ai
Subject: Re: Non-monotonic reasoning and truth maintenance systems
Message-ID: <8611131506.AA01658@watdragon.uucp>
Date: Thu, 13-Nov-86 10:06:11 EST
Article-I.D.: watdrago.8611131506.AA01658
Posted: Thu Nov 13 10:06:11 1986
Date-Received: Wed, 19-Nov-86 06:08:06 EST
References: <8611120808.AA14610@ucbvax.Berkeley.EDU>
Sender: daemon@ucbvax.BERKELEY.EDU
Organization: The ARPA Internet
Lines: 26
Approved: ailist@sri-stripe.arpa

> "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