Prime Implicate Normal Form for ALC Concepts

Meghyn BienvenuMeghyn Bienvenu

Download

Meghyn Bienvenu
Prime Implicate Normal Form for ALC Concepts
Proceedings of the Twenty-Third Conference on Artificial Intelligence (AAAI-08), 412-417, 2008. AAAI Press

Details
Bibtex

KurzfassungAbstract
In this paper, we present a normal form for concept expressions in the description logic ALC which is based on a recently introduced notion of prime implicate for the modal logic K. We show that concepts in prime implicate normal form enjoy a number of interesting properties. In particular, we prove that subsumption between ALC concepts in prime implicate normal form can be carried out in polynomial time using a simple structural subsumption algorithm reminiscent of those used for less expressive description logics. We provide a sound and complete algorithm for putting concepts into prime implicate normal form, and we investigate the spatial complexity of this transformation, showing there to be an at most doubly-exponential blowup in concept length. At the end of the paper, we compare prime implicate normal form to two other normal forms for ALC, discussing the relative merits of the different approaches.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BienvenuAAAI08,
  author = {Meghyn {Bienvenu}},
  booktitle = {Proceedings of the Twenty-Third Conference on Artificial Intelligence (AAAI-08)},
  pages = {412--417},
  publisher = {AAAI Press},
  title = {Prime Implicate Normal Form for {$\mathcal{ALC}$} Concepts},
  year = {2008},
}