It’s Not My Default: The Complexity of Membership Problems in Restricted Propositional Default Logics

Jonathan Stillman

We investigate the computational complexity of membership problems in a number of propositional default logics. We introduce a hierarchy of classes of propositional default rules that extends that described in [Kautz and Selman 1989], and characterize the complexity of membership problems in these classes under various simplifying assumptions about the underlying propositional theory. Our work significantly extends both that presented in [Kautz and Selman 1989] and in [Stillman 199Oa].


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.