Model Checking for Nonmonotonic Logics: Algorithms and Complexity
Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence. Automated Reasoning. Pages 76-82.
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.
@inproceedings{ijcai1999p12,
title = {Model Checking for Nonmonotonic Logics: Algorithms and Complexity},
author = {Rosati, Riccardo},
booktitle = {Proceedings of the Sixteenth International Joint Conference on
Artificial Intelligence, {IJCAI-99}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Thomas Dean},
pages = {76--82},
year = {1999},
note = {Automated Reasoning},
url = {https://ijcai.org/proceedings/1999/12},
}
TY - CPAPER TI - Model Checking for Nonmonotonic Logics: Algorithms and Complexity AU - Rosati, Riccardo T2 - Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, IJCAI-99 PB - International Joint Conferences on Artificial Intelligence PY - 1999 SP - 76 EP - 82 UR - https://ijcai.org/proceedings/1999/12 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
