Hybrid Unification in the Description Logic EL

From International Center for Computational Logic

Toggle side column
Franz Baader, Oliver Fernández Gil, Barbara Morawska
Hybrid Unification in the Description Logic EL
In Pascal Fontaine and Christophe Ringeissen and Renate A. Schmidt, eds., Proceedings of the 9th International Symposium on Frontiers of Combining Systems (FroCoS 2013), volume 8152 of Lecture Notes in Computer Science, 295-310, September 2013. Springer
  • KurzfassungAbstract
    Unification in Description Logics (DLs) has been proposed as an inference service that can, for example, be used to detect redundancies in ontologies. For the DL EL, which is used to define several large biomedical ontologies, unification is NP-complete. However, the unification algorithms for EL developed until recently could not deal with ontologies containing general concept inclusions (GCIs). In a series of recent papers we have made some progress towards addressing this problem, but the ontologies the developed unification algorithms can deal with need to satisfy a certain cycle restriction. In the present paper, we follow a different approach. Instead of restricting the input ontologies, we generalize the notion of unifiers to so-called hybrid unifiers. Whereas classical unifiers can be viewed as acyclic TBoxes, hybrid unifiers are cyclic TBoxes, which are interpreted together with the ontology of the input using a hybrid semantics that combines fixpoint and descriptive semantics. We show that hybrid unification in EL is NP-complete and introduce a goal-oriented algorithm for computing hybrid unifiers.
  • Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
The final publication is available at Springer.
@inproceedings{ BaFM-FroCoS13,
  address = {Nancy, France},
  author = {Franz {Baader} and Oliver {Fern\'andez Gil} and Barbara {Morawska}},
  booktitle = {Proceedings of the 9th International Symposium on Frontiers of Combining Systems ({FroCoS 2013})},
  editor = {Pascal {Fontaine} and Christophe {Ringeissen} and Renate A. {Schmidt}},
  month = {September},
  pages = {295--310},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Computer Science},
  title = {Hybrid Unification in the Description Logic {$\mathcal{EL}$}},
  volume = {8152},
  year = {2013},