LATPub240: 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 1: | Zeile 1: | ||
{{Publikation Erster Autor | {{Publikation Erster Autor | ||
|ErsterAutorVorname= | |ErsterAutorVorname=Franz | ||
|ErsterAutorNachname=Baader | |ErsterAutorNachname=Baader | ||
|FurtherAuthors= | |FurtherAuthors=Anni-Yasmin Turhan | ||
}} | }} | ||
{{Inproceedings | {{Inproceedings | ||
| Zeile 20: | Zeile 20: | ||
}} | }} | ||
{{Publikation Details | {{Publikation Details | ||
|Abstract= | |Abstract= For Description Logics with existential restrictions, the size of the least common subsumer (lcs) of concept descriptions may grow exponentially in the size of the input descriptions. The first (negative) result presented in this paper is that it is in general not possible to express the exponentially large concept description representing the lcs in a more compact way by using an appropriate (acyclic) terminology. In practice, a second and often more severe cause of complexity was the fact that concept descriptions containing concepts defined in a terminology must first be unfolded (by replacing defined names by their definition) before the known lcs algorithms could be applied. To overcome this problem, we present a modified lcs algorithm that performs lazy unfolding, and show that this algorithm works well in practice. | ||
|ISBN= | |ISBN= | ||
|ISSN= | |ISSN= | ||
| Zeile 53: | Zeile 38: | ||
year = {2002}, | year = {2002}, | ||
} | } | ||
}} | }} | ||
Aktuelle Version vom 25. März 2015, 16:34 Uhr
On the problem of computing small representations of least common subsumers
Franz BaaderFranz Baader, Anni-Yasmin TurhanAnni-Yasmin Turhan
Franz Baader, Anni-Yasmin Turhan
On the problem of computing small representations of least common subsumers
Proceedings of the German Conference on Artificial Intelligence, 25th German Conference on Artificial Intelligence (KI 2002), Lecture Notes in Artificial Intelligence, 2002. Springer
On the problem of computing small representations of least common subsumers
Proceedings of the German Conference on Artificial Intelligence, 25th German Conference on Artificial Intelligence (KI 2002), Lecture Notes in Artificial Intelligence, 2002. Springer
- KurzfassungAbstract
For Description Logics with existential restrictions, the size of the least common subsumer (lcs) of concept descriptions may grow exponentially in the size of the input descriptions. The first (negative) result presented in this paper is that it is in general not possible to express the exponentially large concept description representing the lcs in a more compact way by using an appropriate (acyclic) terminology. In practice, a second and often more severe cause of complexity was the fact that concept descriptions containing concepts defined in a terminology must first be unfolded (by replacing defined names by their definition) before the known lcs algorithms could be applied. To overcome this problem, we present a modified lcs algorithm that performs lazy unfolding, and show that this algorithm works well in practice. - Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory
@inproceedings{ BaaderTurhan-KI02,
address = {Aachen, Germany},
author = {F. {Baader} and A.-Y. {Turhan}},
booktitle = {Proceedings of the German Conference on Artificial Intelligence, 25th German Conference on Artificial Intelligence (KI 2002)},
publisher = {Springer--Verlag},
series = {Lecture Notes in Artificial Intelligence},
title = {On the problem of computing small representations of least common subsumers},
year = {2002},
}
