Pushing the EL Envelope

Baader, Brandt, and Lutz

el description logic complexity reasoning subsumption

@inproceedings{baader:ijcai-2005,
  author={Franz Baader and Sebastian Brandt and Carsten Lutz},
  title={Pushing the \mathcal{EL} Envelope},
  booktitle={In Proc. of IJCAI 2005},
  year={2005},
  pages={364--369}
}

Motivated by favorable results for EL, especially compared to other simple languages

• Tractability here taken as polynomial time decidable
• FL_0: Conjunction and value restrictions
  • Intractable w/ addition of acyclic TBoxes
• EL: Conjunction and existential restrictions
  • Remains tractable even with general concept inclusion axioms

Value restrictions were initially focused on simply because that was the semantics people applied to slots in frame languages

• After it became clear that intractability was largely unavoidable, research drifted toward more expressive languages that had reasonable practical performance

EL and some minor extensions can be very useful for many applications

• SNOMED uses EL with an acyclic TBox
• Large portions of Galen can be covered by EL with GCIs & transitive roles
• The Gene Ontology is essentially an acyclic EL TBox w/ one transitive role

Paper starts w/ EL+GCIs and adds many constructs while maintaining tractability, creating the language EL++

• Bottom concept (disjointness)
• Nominals (singleton concepts)
• Restricted concrete domains (numbers and strings)
• Restricted role-value maps
  • Needed for transitivity, right-identity rule

Essentially all other additions lead to intractability or EXPTime-hardness