Reasoning with Minimal Belief and Negation as Failure: Algorithms and Complexity

Riccardo Rosati.
In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI'97), pages 430-435, AAAI Press/The MIT Press, 1997.

Abstract:

We study the computational properties of the propositional fragment of MBNF, the logic of minimal belief and negation as failure introduced by Lifschitz, which can be considered as a unifying framework for several nonmonotonic formalisms, including default logic, autoepistemic logic, circumscription, epistemic queries and logic programming. We characterize the complexity and provide algorithms for reasoning in propositional MBNF. In particular, we show that skeptical entailment in propositional MBNF is Π^p_3-complete, hence, it is harder than reasoning in all the above mentioned propositional formalisms for nonmonotonic reasoning. We also prove the exact correspondence between negation as failure in MBNF and negative introspection in Moore's autoepistemic logic.

Bibtex entry:

@String{AAAI-97 = "Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI'97)"}

@String{AAAIP = "{AAAI} Press/The {MIT} Press"}

@Inproceedings{Rosa97,
author = "Riccardo Rosati",
title = "Reasoning with Minimal Belief and Negation as Failure: {A}lgorithms and Complexity",
booktitle = AAAI-97,
pages = "430--435",
publisher = AAAIP,
year = 1997,
}