It's not my default: the complexity of membership problems in restricted propositional default logics
Jonathan Stillman · National Conference on Artificial Intelligence · 1990
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 1990a].