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