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.