Reasoning with Parsimonious and Moderately Grounded Expansions

Article type: Research Article

Authors: Eiter, Thomas | Gottlob, Georg^{; *}

Affiliations: Christian Doppler Laboratory for Expert Systems, Technical University of Vienna, Paniglgasse 16, A-1040 Wien, Austria

Note: [*] Internet E-mails: [email protected], [email protected]

Abstract: We investigate the complexity of autoepistemic reasoning with parsimonious and moderately grounded expansions. A stable expansion of an autoepistemic set of premises is parsimonious if its objective (i.e. nonmodal) part does not contain the objective part of any other stable expansion. We prove that deciding whether a formula φ belongs to at least one parsimonious stable expansion of a finite base set A is complete for Σ3P, while deciding containment in all parsimonious stable expansions is complete for ∏3P. Similar results are derived for autoepistemic reasoning with moderately grounded expansions. In particular, we show that deciding whether a formula φ belongs to some moderately grounded expansion of a finite base set A is Σ3P-complete, and that deciding whether φ belongs to all moderately grounded expansions is ∏3P-complete. These results suggest that reasoning with parsimonious stable expansions and moderately grounded expansions is strictly harder than reasoning in Moore’s standard version of autoepistemic logic. We also address the complexity of reasoning if the set A is in a normalized form, and derive completeness results for this case.

DOI: 10.3233/FI-1992-171-204

Journal: Fundamenta Informaticae, vol. 17, no. 1-2, pp. 31-53, 1992