Piero A. Bonatti, Carsten Lutz, Frank Wolter:
Description Logics with Circumscription.
Abstract
We show that circumscription can be used to extend description
logics (DLs) with non-monotonic features in a straightforward and
transparent way. In particular, we consider extensions with
circumscription of the expressive DLs ALCIO and ALCQO and prove that
reasoning in these logics is decidable under a simple restriction: only
concept names can be circumscribed, and role names vary freely during
circumscription. We pinpoint the exact computational complexity of
reasoning as complete for NPNEXP and NEXPNP, depending on whether or not
the number of minimized and fixed predicates is assumed to be bounded by a
constant. We also show that we cannot allow role names to be fixed during
minimization rather than having them vary: this modification renders
reasoning undecidable already in the basic DL ALC. Finally, we argue that
non-monotonic DLs based on circumscription are an appropriate tool for
modelling defeasible inheritance. In particular, we can avoid the
restriction of non-monotonic reasoning to domain elements that are named
by an individual constant, as adopted by other non-monotonic DLs.
URL:
http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2006-023
@inproceedings{REWERSE-RP-2006-023, author = {Piero A. Bonatti and Carsten Lutz and Frank Wolter}, title = {Description Logics with Circumscription}, booktitle = {Proceedings of 10th International Conference on Principles of Knowledge Representation and Reasoning, Lake District of the UK (2nd--5th June 2006)}, year = {2006}, pages = {400--410}, url = {http://rewerse.net/publications/rewerse-publications.html#REWERSE-RP-2006-023} }