Model checking for nonmonotonic logics: Algorithms and complexity

Riccardo Rosati.
In Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI'99), pages 76-81, Morgan Kaufmann, Los Altos, 1999. ISBN 1-55860-613-0.

Abstract:

We study the complexity of model checking in propositional nonmonotonic logics. Specifically, we first define the problem of model checking in such formalisms, based on the fact that several nonmonotonic logics make use of interpretation structures (i.e., default extensions, stable expansions, universal Kripke models) which are more complex than standard interpretations of propositional logic. Then, we analyze the complexity of checking whether a given interpretation structure satisfies a nonmonotonic theory. In particular, we characterize the complexity of model checking for Reiter's default logic and its restrictions, Moore's autoepistemic logic, and several nonmonotonic modal logics. The results obtained show that, in all such formalisms, model checking is computationally easier than logical inference.

Bibtex entry:

@String{IJCAI-99 = "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence (IJCAI'99)"}

@String{MK = "Morgan Kaufmann, Los Altos"}

@Inproceedings{Rosa99b,
author = "Riccardo Rosati",
title = "Model checking for nonmonotonic logics: {A}lgorithms and complexity",
booktitle = IJCAI-99,
pages = "76--81",
publisher = MK,
year = 1999,
isbn = "1-55860-613-0",
}