Donald Bren School of Information and Computer Sciences

This paper focuses on network default theories. Etherington [Etherington, 1987] has established a correspondence between inheritance networks with exceptions and a subset of Reiters 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 propositional 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 techniques can be used to compute extensions and to identify tractable network default theories. For any propositional network theory, our algorithms compute all its extensions and verifies if a given conclusion is in one or all extensions.