Conservative Extensions in the Lightweight Description Logic EL

Carsten LutzCarsten Lutz, Frank WolterFrank Wolter

Download

Carsten Lutz, Frank Wolter
Conservative Extensions in the Lightweight Description Logic EL
In Frank Pfenning, eds., Proceedings of the 21th Conference on Automated Deduction (CADE-21), volume 4603 of Lecture Notes in Artificial Intelligence, 84-99, 2007. Springer

Details
Bibtex

KurzfassungAbstract
We bring together two recent trends in description logic (DL): lightweight DLs in which the subsumption problem is tractable and conservative extensions as a central tool for formalizing notions of ontology design such as refinement and modularity. Our aim is to investigate conservative extensions as an automated reasoning problem for the basic tractable DL EL. The main result is that deciding (deductive) conservative extensions is ExpTime-complete, thus more difficult than subsumption in EL, but not more difficult than subsumption in expressive DLs. We also show that if conservative extensions are defined model-theoretically, the associated decision problem for EL is undecidable.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ Lutz-Wolter-CADE-07,
  author = {Carsten {Lutz} and Frank {Wolter}},
  booktitle = {Proceedings of the 21th Conference on Automated Deduction (CADE-21)},
  editor = {Frank {Pfenning}},
  pages = {84--99},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Conservative Extensions in the Lightweight Description Logic $\mathcal{EL}$},
  volume = {4603},
  year = {2007},
}