Pushing the EL Envelope

Franz BaaderFranz Baader, Sebastian BrandtSebastian Brandt, Carsten LutzCarsten Lutz

Download

Franz Baader, Sebastian Brandt, Carsten Lutz
Pushing the EL Envelope
Technical Report, Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology, volume LTCS-05-01, 2005. LTCS-Report

Details
Bibtex

KurzfassungAbstract
Recently, it has been shown that the small 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 w.r.t. general concept inclusion axioms (GCIs). On the one hand, we will 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 will show that basically all other additions of typical DL constructors to EL with GCIs make subsumption intractable, and in most cases even ExpTime-complete. In addition, we will show that subsumption in FL0 with GCIs is ExpTime complete.
Bemerkung: Note: See http://lat.inf.tu-dresden.de/research/reports.html.
Forschungsgruppe:Research Group: AutomatentheorieAutomata Theory

@techreport{ BaaderBrandtLutz-LTCS-05-01,
  address = {Germany},
  author = {F. {Baader} and S. {Brandt} and C. {Lutz}},
  institution = {Chair for Automata Theory, Institute for Theoretical Computer Science, Dresden University of Technology},
  note = {See http://lat.inf.tu-dresden.de/research/reports.html.},
  number = {LTCS-05-01},
  title = {Pushing the EL Envelope},
  type = {LTCS-Report},
  year = {2005},
}