dlm.allegra@btl.CSNET.UUCP (04/23/87)
May 7th 10:30 AM
AT&T Bell Laboratories - Murray Hill 1E-449
REPORTING THE NON-MONOTONIC NEWS:
Keeping the Beat Local
Benjamin Grosof
Stanford University
"Non-monotonic" reasoning systems are ones in which some conclusions
have a default or retractable status. A prime motivation for such
systems is to build agents that revise their beliefs in response to
news from their environment. Efficient updating is problematic,
however, because adding new information in general may require the
revision of many, or even all, previous retractable conclusions. An
understanding is needed of the "partial monotonicities" of updating,
i.e. of the irrelevance of updates to parts of the previous
retractable conclusions.
To define non-monotonic theories, we introduce a formalism based on
McCarthy's circumscription that directly expresses, as axioms, both
default beliefs and preferences among default beliefs. It has a
strong semantics based on first- and second-order logic. We
characterize non-monotonic theories as hierarchically decomposable
in a manner more analogous to programming languages than to ordinary
monotonic logics. We then give a set of results about partial
monotonicities of updating. We discover some surprising differences
between updates consisting of default axioms and those consisting of
non-retractable axioms. These results bear on a wide variety of
applications of non-monotonic reasoning.
Sponsor: R.J.Brachman