LATPub595: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| (2 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt) | |||
| Zeile 6: | Zeile 6: | ||
{{Inproceedings | {{Inproceedings | ||
|Referiert=1 | |Referiert=1 | ||
|Title=Matching with respect to general concept inclusions in the Description Logic | |Title=Matching with respect to general concept inclusions in the Description Logic EL | ||
|Year=2014 | |Year=2014 | ||
|Month= | |Month= | ||
|Booktitle=Proceedings of the 27th International Workshop on Description Logics ( | |Booktitle=Proceedings of the 27th International Workshop on Description Logics (DL'14) | ||
|Editor=Meghyn | |Editor=Meghyn Bienvenu and Magdalena Ortiz and Riccardo Rosati and Mantas Simkus | ||
|Note= | |Note= | ||
|Organization= | |Organization= | ||
|Pages=33 | |Pages=33-44 | ||
|Publisher= | |Publisher= | ||
|Series=CEUR Workshop Proceedings | |Series=CEUR Workshop Proceedings | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Matching concept descriptions against concept patterns | |Abstract=Matching concept descriptions against concept patterns wasintroduced as a new inference task in Description Logics (DLs) almost20 years ago, motivated by applications in the Classic system. For theDL EL, it was shown in 2000 that the matching problem is NP-complete.It then took almost 10 years before this NP-completeness result couldbe extended from matching to unification in EL. The next big challengewas then to further extend these results from matching and unificationwithout 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 showsome partial results for general TBoxes that satisfy a certain restrictionon cyclic dependencies between concepts, but the general case is stillopen. For matching, we solve the general case in this paper: we show thatmatching in EL w.r.t. general TBoxes is NP-complete by introducing agoal-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. | ||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 40: | Zeile 40: | ||
year = {2014}, | year = {2014}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
Matching with respect to general concept inclusions in the Description Logic EL
Franz BaaderFranz Baader, Barbara MorawskaBarbara Morawska
Franz Baader, Barbara Morawska
Matching with respect to general concept inclusions in the Description Logic EL
In Meghyn Bienvenu and Magdalena Ortiz and Riccardo Rosati and Mantas Simkus, eds., Proceedings of the 27th International Workshop on Description Logics (DL'14), volume 1193 of CEUR Workshop Proceedings, 33-44, 2014
Matching with respect to general concept inclusions in the Description Logic EL
In Meghyn Bienvenu and Magdalena Ortiz and Riccardo Rosati and Mantas Simkus, eds., Proceedings of the 27th International Workshop on Description Logics (DL'14), volume 1193 of CEUR Workshop Proceedings, 33-44, 2014
- KurzfassungAbstract
Matching concept descriptions against concept patterns wasintroduced as a new inference task in Description Logics (DLs) almost20 years ago, motivated by applications in the Classic system. For theDL EL, it was shown in 2000 that the matching problem is NP-complete.It then took almost 10 years before this NP-completeness result couldbe extended from matching to unification in EL. The next big challengewas then to further extend these results from matching and unificationwithout 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 showsome partial results for general TBoxes that satisfy a certain restrictionon cyclic dependencies between concepts, but the general case is stillopen. For matching, we solve the general case in this paper: we show thatmatching in EL w.r.t. general TBoxes is NP-complete by introducing agoal-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. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ BaMo-DL14,
address = {Vienna, Austria},
author = {Franz {Baader} and Barbara {Morawska}},
booktitle = {Proceedings of the 27th International Workshop on Description Logics ({DL'14})},
editor = {Meghyn {Bienvenu} and Magdalena {Ortiz} and Riccardo {Rosati} and Mantas {Simkus}},
pages = {33--44},
series = {CEUR Workshop Proceedings},
title = {Matching with respect to general concept inclusions in the Description Logic $\mathcal{EL}$},
volume = {1193},
year = {2014},
}
