| Authors: |
Franz Baader
and Sebastian Brandt
and Carsten Lutz
|
| URL: |
http://www.ijcai.org/papers/0372.pdf |
| Description: |
Basis of the EL++ tractable fragment of the OWL1.1 submission |
| Tags: |
descriptionlogic
owl
owl1.1
semanticweb
|
| 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. |
@inproceedings{el++,
title = {Pushing the EL Envelope},
author = {Franz Baader and Sebastian Brandt and Carsten Lutz},
booktitle = {International Joint Conferences on Artificial Intelligence (IJCAI-05)},
url = {http://www.ijcai.org/papers/0372.pdf},
year = {2005},
description = {Basis of the EL++ tractable fragment of the OWL1.1 submission},
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.},
keywords = {descriptionlogic owl owl1.1 semanticweb }
}
::