(Non-)Succinctness of uniform interpolants of general terminologies in the description logic ℰℒ

Nadeschda NikitinaNadeschda Nikitina, Sebastian RudolphSebastian Rudolph

Nadeschda Nikitina, Sebastian Rudolph
(Non-)Succinctness of uniform interpolants of general terminologies in the description logic ℰℒ
Artificial Intelligence, 215:120-140, October 2014

Details
Bibtex

KurzfassungAbstract
ℰℒ is a popular description logic, used as a core formalism in large existing knowledge bases. Uniform interpolants of knowledge bases are of high interest, e.g. in scenarios where a knowledge base is supposed to be partially reused. However, to the best of our knowledge no procedure has yet been proposed that computes uniform ℰℒ interpolants of general ℰℒ terminologies. Up to now, also the bound on the size of uniform ℰℒ interpolants has remained unknown. In this article, we propose an approach to computing a finite uniform interpolant for a general ℰℒ terminology if it exists. To this end, we develop a quadratic representation of ℰℒ TBoxes as regular tree grammars. Further, we show that, if a finite uniform ℰℒ interpolant exists, then there exists one that is at most triple exponential in the size of the original TBox, and that, in the worst case, no smaller interpolants exist, thereby establishing tight worst-case bounds on their size. Beyond showing these bounds, the notions and results established in this paper also provide useful insights for designing efficient ontology reformulation algorithms, for instance, within the context of module extraction.
Weitere Informationen unter:Further Information: Link
Forschungsgruppe:Research Group: Computational LogicComputational Logic

@article{NR2014,
  author  = {Nadeschda Nikitina and Sebastian Rudolph},
  title   = {(Non-)Succinctness of uniform interpolants of general terminologies
             in the description logic {$\mathcal{EL}$}},
  journal = {Artificial Intelligence},
  volume  = {215},
  year    = {2014},
  month   = {October},
  pages   = {120-140},
  doi     = {10.1016/j.artint.2014.06.005}
}