A Goal-Oriented Algorithm for Unification in EL w.r.t. Cycle-Restricted TBoxes

Franz BaaderFranz Baader,  Stefan BorgwardtStefan Borgwardt,  Barbara MorawskaBarbara Morawska
Franz Baader, Stefan Borgwardt, Barbara Morawska
A Goal-Oriented Algorithm for Unification in EL w.r.t. Cycle-Restricted TBoxes
In Yevgeny Kazakov and Domenico Lembo and Frank Wolter, eds., Proceedings of the 25th International Workshop on Description Logics (DL'12), volume 846 of CEUR Workshop Proceedings, 37-47, 2012
• KurzfassungAbstract
Unification in Description Logics (DLs) has been proposed as an 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 been shown to be NP-complete, and thus of significantly lower complexity than unification in other DLs of similarly restricted expressive power. Recently, a brute-force NP-unification algorithm for EL w.r.t. a restricted form of general concept inclusion axioms was developed. This paper introduces a goal-oriented algorithm that reduces the amount of nondeterministic guesses considerably.
• Forschungsgruppe:Research Group: Automatentheorie
@inproceedings{ BaBM-DL-12,
address = {Rome, Italy},
author = {Franz {Baader} and Stefan {Borgwardt} and Barbara {Morawska}},
booktitle = {Proceedings of the 25th International Workshop on Description Logics (DL'12)},
editor = {Yevgeny {Kazakov} and Domenico {Lembo} and Frank {Wolter}},
pages = {37--47},
series = {CEUR Workshop Proceedings},
title = {A Goal-Oriented Algorithm for Unification in {$\mathcal{EL}$} w.r.t. Cycle-Restricted {TB}oxes},
volume = {846},
year = {2012},
}