Pushing the EL Envelope Further

Franz BaaderFranz Baader, Sebastian BrandtSebastian Brandt, Carsten LutzCarsten Lutz

Download

Franz Baader, Sebastian Brandt, Carsten Lutz
Pushing the EL Envelope Further
In Kendall Clark and Peter F. Patel-Schneider, eds., In Proceedings of the OWLED 2008 DC Workshop on OWL: Experiences and Directions, 2008

Details
Bibtex

KurzfassungAbstract
We extend the description logic EL++ with reflexive roles and range restrictions, and show that subsumption remains tractable if a certain syntactic restriction is adopted. We also show that subsumption becomes PSpace-hard (resp. undecidable) if this restriction is weakened (resp. dropped). Additionally, we prove that tractability is lost when symmetric roles are added: in this case, subsumption becomes ExpTime- hard.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@inproceedings{ BaaderEtAl-OWLED08DC,
  author = {Franz {Baader} and Sebastian {Brandt} and Carsten {Lutz}},
  booktitle = {In Proceedings of the OWLED 2008 DC Workshop on OWL: Experiences and Directions},
  editor = {Kendall {Clark} and Peter F. {Patel-Schneider}},
  title = {Pushing the EL Envelope Further},
  year = {2008},
}