Unification in the Description Logic EL without the Top Concept

Franz BaaderFranz Baader, Nguyen Thanh BinhNguyen Thanh Binh, Stefan BorgwardtStefan Borgwardt, Barbara MorawskaBarbara Morawska

Download

Franz Baader, Nguyen Thanh Binh, Stefan Borgwardt, Barbara Morawska
Unification in the Description Logic EL without the Top Concept
In Nikolaj Bjørner and Viorica Sofronie-Stokkermans, eds., Proceedings of the 23rd International Conference on Automated Deduction (CADE 2011), volume 6803 of Lecture Notes in Computer Science, 70-84, 2011. Springer

Details
Bibtex

KurzfassungAbstract
Unification in Description Logics has been proposed as a novel inference service that can, for example, be used to detect redundancies in ontologies. The inexpressive Description Logic EL is of particular interest in this context since, on the one hand, several large biomedical ontologies are defined using EL. On the other hand, unification in EL has recently been shown to be NP-complete, and thus of considerably lower complexity than unification in other DLs of similarly restricted expressive power. However, EL allows the use of the top concept, which represents the whole interpretation domain, whereas the large medical ontology SNOMED CT makes no use of this feature. Surprisingly, removing the top concept from EL makes the unification problem considerably harder. More precisely, we will show in this paper that unification in EL without the top concept is PSpace-complete.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaBiBoMoCADE11,
  address = {Wroclaw, Poland},
  author = {Franz {Baader} and Nguyen Thanh {Binh} and Stefan {Borgwardt} and Barbara {Morawska}},
  booktitle = {Proceedings of the 23rd International Conference on Automated Deduction ({CADE 2011})},
  editor = {Nikolaj {Bj{\o}rner} and Viorica {Sofronie-Stokkermans}},
  pages = {70--84},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Unification in the Description Logic $\mathcal{EL}$\\ without the Top Concept},
  volume = {6803},
  year = {2011},
}