Semantisches Browsen

Aus International Center for Computational Logic
Wechseln zu:Navigation, Suche
LATPub502
Abstract Unification has been investigated both in
Unification has been investigated both in modal logics and in description logics, albeit with different motivations. In description logics, unification can be used to detect redundancies in ontologies. In this context, it is not sufficient to decide unifiability, one must also compute appropriate unifiers and present them to the user. For the description logic EL, which is used to define several large biomedical ontologies, deciding unifiability is an NP-complete problem. It is known that every solvable EL-unification problem has a minimal unifier, and that every minimal unifier is a local unifier. Existing unification algorithms for EL compute all minimal unifiers, but additionally (all or some) non-minimal local unifiers. Computing only the minimal unifiers would be better since there are considerably less minimal unifiers than local ones, and their size is usually also quite small. In this paper we investigate the question whether the known algorithms for EL-unification can be modified such that they compute exactly the minimal unifiers without changing the complexity and the basic nature of the algorithms. Basically, the answer we give to this question is negative.
swer we give to this question is negative.  +
Author Franz Baader + , Stefan Borgwardt + , Barbara Morawska +
BibTex
@inproceedings{ BaBM-AiML12,
  author = {Franz {Baader} and Stefan {Borgwardt} and Barbara {Morawska}},
  booktitle = {Proceedings of the 9-th International Conference on Advances in Modal Logic ({AiML'12})},
  editor = {Silvio {Ghilardi} and Lawrence {Moss}},
  title = {Computing Minimal {$\mathcal{EL}$}-unifiers is Hard},
  year = {2012},
}
Bibtype Inproceedings  +
Booktitle Proceedings of the 9-th International Conference on Advances in Modal Logic (AiML'12)  +
Download BaBM-AiML12.pdf  +
Editor Silvio Ghilardi and Lawrence Moss  +
ErsterAutorNachname Baader  +
ErsterAutorVorname Franz  +
Forschungsgruppe Automatentheorie +
Publication text Franz Baader, Stefan Borgwardt, Barbara Mo
Franz Baader, Stefan Borgwardt, Barbara Morawska<br/> '''[[LATPub502|<b>Computing Minimal EL-unifiers is Hard</b>]]''' <br/>__NOTOC__In Silvio Ghilardi and Lawrence Moss, eds., <i>Proceedings of the 9-th International Conference on Advances in Modal Logic (AiML'12)</i>, 2012<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[LATPub502|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:BaBM-AiML12.pdf|Download]]
pan> [[Media:BaBM-AiML12.pdf|Download]]  +
Publication text en Franz Baader, Stefan Borgwardt, Barbara Mo
Franz Baader, Stefan Borgwardt, Barbara Morawska<br/> '''[[LATPub502/en|<b>Computing Minimal EL-unifiers is Hard</b>]]''' <br/>__NOTOC__In Silvio Ghilardi and Lawrence Moss, eds., <i>Proceedings of the 9-th International Conference on Advances in Modal Logic (AiML'12)</i>, 2012<br/><span class="glyphicon glyphicon-chevron-right" style="font-size: 85%;" ></span> [[LATPub502|Details]] <span class="glyphicon glyphicon-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:BaBM-AiML12.pdf|Download]]
pan> [[Media:BaBM-AiML12.pdf|Download]]  +
Referiert 1  +
Title Computing Minimal EL-unifiers is Hard  +
To appear 0  +
Type inproceedings  +
Year 2012  +
Hat Abfrage
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
LATPub502 + , LATPub502 + , LATPub502 + , LATPub502 + , LATPub502 + , LATPub502 + , LATPub502 +
Kategorien Inproceedings , Publikation
Zuletzt geändert
Dieses Attribut ist ein Spezialattribut in diesem Wiki.
25 März 2015 14:34:07  +
verstecke Attribute die hierhin verlinken 
LATPub502/en + Weiterleitungsseite
 

 

Bitte den Namen einer Seite angeben, um mit dem Browsen zu beginnen.