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
Technical Report, Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universität Dresden, volume 14-03, 2014. LTCS-Report

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 the matching problem is NP-complete. It then took almost 10 years before this NP-completeness result could be extended from matching to unification in EL. The next big challenge was then to further extend these results from matching and unification without a TBox to matching and unification w.r.t. a general TBox, i.e., a finite set of general concept inclusions. For unification, we could show some partial results for general TBoxes that satisfy a certain restriction on cyclic dependencies between concepts, but the general case is still open. For matching, we solve the general case in this paper: we show that matching in EL w.r.t. general TBoxes is NP-complete 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.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BaMo-LTCS-14-3,
  address = {Dresden, Germany},
  author = {Franz {Baader} and Barbara {Morawska}},
  institution = {Chair of Automata Theory, Institute of Theoretical Computer Science, Technische Universit{\"a}t Dresden},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {14-03},
  title = {Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$},
  type = {LTCS-Report},
  year = {2014},
}