Reasoning with Parsimonious and Moderately Grounded Expansions

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 ${\mathrm{\Sigma }}_3^{\mathit{P}}$ , while deciding containment in all parsimonious stable expansions is complete for ${\prod }_3^{\mathit{P}}$ . 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 ${\mathrm{\Sigma }}_3^{\mathit{P}}$ -complete, and that deciding whether φ belongs to all moderately grounded expansions is ${\prod }_3^{\mathit{P}}$ -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.