F. Baader, S. Brandt, and C. Lutz. International Joint Conferences on Artificial Intelligence (IJCAI-05), (2005)
Abstract
Recently, it has been shown that the small description
logic (DL) EL, which allows for conjunction
and existential restrictions, has better algorithmic
properties than its counterpart FL0, which allows
for conjunction and value restrictions. Whereas the
subsumption problem in FL0 becomes already intractable
in the presence of acyclic TBoxes, it remains
tractable in EL even with general concept
inclusion axioms (GCIs). On the one hand, we extend
the positive result for EL by identifying a set
of expressive means that can be added to EL without
sacrificing tractability. On the other hand, we
show that basically all other additions of typical
DL constructors to EL with GCIs make subsumption
intractable, and in most cases even EXPTIMEc omplete.
In addition, we show that subsumption
in FL0 with GCIs is EXPTIME-complete.
Description
Basis of the EL++ tractable fragment of the OWL1.1 submission
%0 Conference Paper
%1 BaaderBrandtLutz_2005
%A Baader, Franz
%A Brandt, Sebastian
%A Lutz, Carsten
%B International Joint Conferences on Artificial Intelligence (IJCAI-05)
%D 2005
%K completion el reasoning
%T Pushing the EL Envelope
%U http://www.ijcai.org/papers/0372.pdf
%X Recently, it has been shown that the small description
logic (DL) EL, which allows for conjunction
and existential restrictions, has better algorithmic
properties than its counterpart FL0, which allows
for conjunction and value restrictions. Whereas the
subsumption problem in FL0 becomes already intractable
in the presence of acyclic TBoxes, it remains
tractable in EL even with general concept
inclusion axioms (GCIs). On the one hand, we extend
the positive result for EL by identifying a set
of expressive means that can be added to EL without
sacrificing tractability. On the other hand, we
show that basically all other additions of typical
DL constructors to EL with GCIs make subsumption
intractable, and in most cases even EXPTIMEc omplete.
In addition, we show that subsumption
in FL0 with GCIs is EXPTIME-complete.
@inproceedings{BaaderBrandtLutz_2005,
abstract = {Recently, it has been shown that the small description
logic (DL) EL, which allows for conjunction
and existential restrictions, has better algorithmic
properties than its counterpart FL0, which allows
for conjunction and value restrictions. Whereas the
subsumption problem in FL0 becomes already intractable
in the presence of acyclic TBoxes, it remains
tractable in EL even with general concept
inclusion axioms (GCIs). On the one hand, we extend
the positive result for EL by identifying a set
of expressive means that can be added to EL without
sacrificing tractability. On the other hand, we
show that basically all other additions of typical
DL constructors to EL with GCIs make subsumption
intractable, and in most cases even EXPTIMEc omplete.
In addition, we show that subsumption
in FL0 with GCIs is EXPTIME-complete.},
added-at = {2013-11-08T15:22:40.000+0100},
author = {Baader, Franz and Brandt, Sebastian and Lutz, Carsten},
biburl = {https://www.bibsonomy.org/bibtex/2c1503c4f44a200582e2d67772485ba11/francesco.k},
booktitle = {International Joint Conferences on Artificial Intelligence (IJCAI-05)},
description = {Basis of the EL++ tractable fragment of the OWL1.1 submission},
interhash = {f4ee93d1af0c5a6dda983862fe239968},
intrahash = {c1503c4f44a200582e2d67772485ba11},
keywords = {completion el reasoning},
timestamp = {2013-11-08T15:23:49.000+0100},
title = {Pushing the EL Envelope},
url = {http://www.ijcai.org/papers/0372.pdf},
year = 2005
}