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 was introduced as a new inference task in Description Logics (DLs) almost 20 years ago, motivated by applications in the Classic system. For the DL EL, 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 introducing a goal-oriented matching algorithm that uses non-deterministic rules to transform a given matching problem into a solved form by a polynomial number of rule applications. We also investigate some tractable variants of 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},
}