clarke@csri.toronto.edu (Jim Clarke) (11/25/88)
AI SEMINAR - Thursday, December 15, 11 a.m. in Room SF 1105
(SF = Sandford Fleming Building, 10 King's College Road)
Drew McDermott
Yale Computer Science Department
"A General Mechanism for Reason Maintenance"
Several sorts of reason-maintenance (aka "truth" maintenance) systems have
been built, distinguished by whether negation is permitted, whether context
switching requires relabeling, how contradiction is handled, and whether
nonmonotonicity is allowed. Several technical and technological issues
must be solved in order to combine the features of all of these systems.
Here is one solution: Let dependencies be clauses (as McAllester does); al-
low literals of the form "Lp" (p is definitely true) to provide for non-
monotonicity; label literals with boolean combinations of assumptions (de-
Kleer), allowing assumptions to be marked as absent (McDermott). The
resulting system automatically mimics Doyle's mechanism for dependency-
directed backtracking. If you want nogoods too, it can be shown that non-
monotonic premises never enter into them, so that nogoods correspond to
classical clauses. These get added to the clause network, thus subsuming
some of deKleer's special propagation rules under standard McAllester-style
boolean propagation. The new clauses never add "odd loops" that would
break the nonmonotonic mechanism.
For those who want practical applications, it will be shown that cryptar-
ithmetic is definitely not one of them.
--
Jim Clarke -- Dept. of Computer Science, Univ. of Toronto, Canada M5S 1A4
(416) 978-4058
BITNET,CSNET: clarke@csri.toronto.edu CDNNET: clarke@csri.toronto.cdn
UUCP: {allegra,cornell,decvax,linus,utzoo}!utcsri!clarke