Matching with respect to general concept inclusions in the Description Logic EL

Franz BaaderFranz Baader, Barbara MorawskaBarbara Morawska

Download

Franz Baader, Barbara Morawska
Matching with respect to general concept inclusions in the Description Logic EL
In Carsten Lutz and Michael Thielscher, eds., Proceedings of the 37th German Conference on Artificial Intelligence (KI'14), volume 8736 of Lecture Notes in Artificial Intelligence, 135-146, 2014. Springer

Details
Bibtex

KurzfassungAbstract
Matching concept descriptions against concept patterns wasintroduced as a new inference task in Description Logics (DLs) almost 20years ago, motivated by applications in the Classic system. For the DLEL, it was shown in 2000 that matching without a TBox is NP-complete.In this paper we show that matching in EL w.r.t. general TBoxes (i.e.,finite sets of general concept inclusions, GCIs) is in NP by introducinga goal-oriented matching algorithm that uses non-deterministic rules totransform a given matching problem into a solved form by a polynomialnumber of rule applications. We also investigate some tractable variantsof the matching problem w.r.t. general TBoxes.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

The final publication is available at Springer.

@inproceedings{ BaMo-KI2014,
  author = {Franz {Baader} and Barbara {Morawska}},
  booktitle = {Proceedings of the 37th German Conference on Artificial Intelligence (KI'14)},
  editor = {Carsten {Lutz} and Michael {Thielscher}},
  pages = {135--146},
  publisher = {Springer-Verlag},
  series = {Lecture Notes in Artificial Intelligence},
  title = {Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$},
  volume = {8736},
  year = {2014},
}