On the problem of computing small representations of least common subsumers

F. BaaderF. Baader, A.-Y. TurhanA.-Y. Turhan

Datei:BaaderTurhan-KI02.ps.gz

Download

F. Baader, A.-Y. 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

Details
Bibtex

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

The final publication is available at Springer.

@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},
}