TBoxes do not yield a compact representation of least common subsumers

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

Datei:BaaderTurhan-DL.ps.gz

Download

F. Baader, A.-Y. Turhan
TBoxes do not yield a compact representation of least common subsumers
Proceedings of the International Workshop in Description Logics 2001 {(DL2001)}, August 2001

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.
 This paper investigates whether the possibly exponentially large 
 concept description representing the lcs can always be represented 
 in a more compact way when using an appropriate (acyclic) TBox for 
 defining this description. 
 This conjecture was supported by our experience
 in a chemical process engineering application. Nevertheless, it
 turns out that, in general, TBoxes cannot always be used to

obtain a polynomial size representation of the lcs.

Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaderTurhan-DL-2001,
  address = {Stanford, USA},
  author = {F. {Baader} and A.-Y. {Turhan}},
  booktitle = {Proceedings of the International Workshop in Description Logics 2001 {(DL2001)}},
  month = {August},
  title = {TBoxes do not yield a compact representation of least common subsumers},
  year = {2001},
}