QUESTION OF THE DAY 					    Friday, December 6
==============================================================================

Briefly summarize the differences between the various kinds of approaches 
to nonmonotonic reasoning (e.g., closed-world assumption, minimal models, 
consistency, epistemic, conditional).

------------------------------------------------------------------------------

Since I got no answers for this one, I've come up with a slightly-more 
detailed set than I was looking for. :)

- Patrick


CLOSED-WORLD ASSUMPTION:  Assumes all relevant information has been 
specified.  Any positive fact not specified is false.  Most obviously 
employed in database theory.  Reiter's (1978) formalization employs a 
definition of closure

   CLOSURE(DB) = DB U {!P(t) | DB !|= P(t), where P is an n-ary
                       predicate symbol of DB and t is an n-tuple
                       of ground terms formed using the function 
                       symbols of DB}

This can generate inconsistent closures in general, though that problem 
is avoided in Horn databases.  Will produce incorrect results in 
databases with null values.

An alternative formalization by Clark (1978) has to do with Prolog 
programs.  His assumption is that sufficient constraints on predicates 
are also sufficient.  This lacks generality; it only works for 
universally quantified clauses; is sensitive to syntactic form.


CONSISTENCY-BASED APPROACHES:  Interpret the absence of information 
prohibiting A to mean that it can consistently be assumed.

Nonmonotonic Logic:  McDermott and Doyle (1980).  Uses a modal operator 
M, with intended semantics MA meaning "A is consistent."  Uses a 
fixed-point operator to define the theorems of a theory A as the 
intersection of all fixed points T for which

   T = Th(A U {Mw | !w not in T}.

Neither the fixed points nor the theory is recursively enumerable.  A 
proof theory is only known for propositional logic. 

Default Logic:  Reiter (1980) treats default conditions as rules of 
inference of the form a(x):b(x)/c(x), meaning "if a(x) is true, and b(x) 
is consistent, infer c(x)."  Default rules generate extensions of the 
theory, also using fixed-points.  E is an extension of a default theory 
(D, W) if E = G(E), where G(S) is the smallest set for which

   1. W c G(S).
   2. G(S) is closed under FOL consequence.
   3. If a:b/c is a default rule of D and a is in G(S) and !b not in S,
      then c in G(S).

Note that extensions are comparable to fixed-points T in nonmonotonic 
logic, but Reiter's interpretation is that they are all possible belief 
sets for an agent; he does not intersect them.

This logic has a proof theory when rules are normal, but the extensions 
are not recursively enumerable, the semantics are unclear, and since 
defaults are expressed as rules, they cannot be reasoned about.


MINIMAL MODEL APPROACHES:  Theorems are sentences that are true in 
distinguished models of the theory.

Circumscription:  Don't get me started.  Predicates P are circumscribed 
with respect to other predicates using a second-order logic axiom, so 
that any minimal theory is one in which the predicates P have the 
narrowest possible definition.

Broadest formalism; has decision theories for versions with constraints.


EPISTEMIC APPROACHES:  Use belief or knowledge to model nonmonotonic 
reasoning.

Autoepistemic Logic:  Based upon nonmonotonic logic, Moore (1984, 1985) 
adds an additional modal operator B for belief.  A set of formulae T is 
defined as a stable expansion of a set A if

   T = Th(A U {Bw | w in T} U {!Bw | w not in T}).

Levesque extends this to first-order case; adds operator O where Ow means 
"w is all that is believed."  Konolige proves that there is an exact 
correspondence between the extensions of default logic and strongly 
grounded expansions of autoepistemic logic.


CONDITIONAL LOGICS:  Use subjunctive conditionals ("If A were the case, 
then B would be the case") to formalize nonmonotonic reasoning.

Not successful approach; such logics are monotonic, also very weak, and 
rely upon pragmatics to achieve nonmonotnic effects, leaving them without 
principled semantics.