R26a  
Influence in Inheritance Networks Using Propositional Logic and Constraint Networks Techniques
Rachel BenEliyahu(rachel@cs.ucla.edu) &
Rina Dechter (dechter@ics.uci.edu)

Abstract This paper focuses on network default theories. Etherington [Etherington, 1987] has established a correspondence between inheritance networks with expections and a subset of Reiter's default logic called network default theories, thus providing a formal semantics and a notion of correct inference for such networks. We show that any such propositional network default theory can be compiled in polynomial time into a classical propositona theory such that the set of models of the latter coincides with the set of extensions of the former. We then show how constraint satisfaction teachniques can be used to compute extensions an to identify tractable network default theories. For any porpositional network theory, our algorithms compute all its extensions and verifies if a given conclusion is in one or all extensions. [ps] [pdf] 