On the Classification and Existence of Structures in Default Logic 1

Abstract

We investigate possible belief sets of an agent reasoning with default rules. Besides of Reiter’s extensions which are based on a proof-theoretic paradigm (similar to Logic Programming), other structures for default theories, based on weaker or different methods of constructing belief sets are considered, in particular, weak extensions and minimal sets. The first of these concepts is known to be closely connected to autoepistemic expansions of Moore, the other to minimal stable autoepistemic theories containing the initial assumptions. We introduce the concept of stratifed collection of default rules and investigate the properties of the largest stratified subset of the family D, determined by W. We find a necessary and sufficient condition for a weak extension to be an extension in terms of stratification. We prove that for theories (D, W) without extension, the least fixed point of the associated operator (with weak extension or minimal set as a context) is an extension of suitably chosen (D’, W) with D’ ⊆ D. We investigate conditions for existence of extensions and introduce the notion of perfectly-stratified set of default rules and its variant of maximally perfectly-stratified set. Existence of such set of default rules turns out to be equivalent to the existence of extension. Finally, we investigate convergence of algorithm for computing extensions.