Pushing the EL Envelope Further.
Franz Baader, Carsten Lutz, Sebastian Brandt · 2008
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.