On the problem of computing small representations of least common subsumers

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

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

On the problem of computing small representations of least common subsumers

On the problem of computing small representations of least common subsumers

Franz BaaderFranz Baader, Anni-Yasmin TurhanAnni-Yasmin Turhan