LATPub319: Unterschied zwischen den Versionen
Aus International Center for Computational Logic
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
Marcel Lippmann (Diskussion | Beiträge) KKeine Bearbeitungszusammenfassung |
||
| Zeile 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname= | |ErsterAutorVorname=Franz | ||
|ErsterAutorNachname=Baader | |ErsterAutorNachname=Baader | ||
|FurtherAuthors=S. Brandt; | |FurtherAuthors=S. Brandt; Carsten Lutz | ||
}} | }} | ||
{{Inproceedings | {{Inproceedings | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract=Recently, it has been shown that the small description logic (DL) EL, | |Abstract=Recently, it has been shown that the small description logic (DL) EL, which allows for conjunction and existential restrictions, has better algorithmic properties than its counterpart FL0, which allows for conjunction and value restrictions. Whereas the subsumption problem in FL0 becomes already intractable in the presence of acyclic TBoxes, it remains tractable in EL even with general concept inclusion axioms (GCIs). On the one hand, we extend the positive result for EL by identifying a set of expressive means that can be added to EL without sacrificing tractability. On the other hand, we show that basically all other additions of typical DL constructors to EL with GCIs make subsumption intractable, and in most cases even ExpTime-complete. In addition, we show that subsumption in FL0 with GCIs is ExpTime-complete. | ||
which allows for conjunction and existential restrictions, has better | |||
algorithmic properties than its counterpart FL0, which allows for | |||
conjunction and value restrictions. Whereas the subsumption problem in | |||
FL0 becomes already intractable in the presence of acyclic TBoxes, it | |||
remains tractable in EL even with general concept inclusion axioms | |||
(GCIs). | |||
identifying a set of expressive means that can be added to EL without | |||
sacrificing tractability. On the other hand, we show that basically | |||
all other additions of typical DL constructors to EL with GCIs make | |||
subsumption intractable, and in most cases even ExpTime-complete. In | |||
addition, we show that subsumption in FL0 with GCIs is | |||
ExpTime-complete. | |||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 50: | Zeile 37: | ||
year = {2005}, | year = {2005}, | ||
} | } | ||
}} | }} | ||
Version vom 23. März 2015, 13:24 Uhr
Pushing the EL Envelope
Franz BaaderFranz Baader, S. BrandtS. Brandt, Carsten LutzCarsten Lutz
Franz Baader, S. Brandt, Carsten Lutz
Pushing the EL Envelope
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence IJCAI-05, 2005. Morgan-Kaufmann Publishers
Pushing the EL Envelope
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence IJCAI-05, 2005. Morgan-Kaufmann Publishers
- KurzfassungAbstract
Recently, it has been shown that the small description logic (DL) EL, which allows for conjunction and existential restrictions, has better algorithmic properties than its counterpart FL0, which allows for conjunction and value restrictions. Whereas the subsumption problem in FL0 becomes already intractable in the presence of acyclic TBoxes, it remains tractable in EL even with general concept inclusion axioms (GCIs). On the one hand, we extend the positive result for EL by identifying a set of expressive means that can be added to EL without sacrificing tractability. On the other hand, we show that basically all other additions of typical DL constructors to EL with GCIs make subsumption intractable, and in most cases even ExpTime-complete. In addition, we show that subsumption in FL0 with GCIs is ExpTime-complete. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ BaaderBrandtLutz-IJCAI-05,
address = {Edinburgh, UK},
author = {F. {Baader} and S. {Brandt} and C. {Lutz}},
booktitle = {Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence {IJCAI-05}},
publisher = {Morgan-Kaufmann Publishers},
title = {Pushing the $\mathcal{EL}$ Envelope},
year = {2005},
}
