Pushing the EL Envelope

By Franz Baader, Sebastian-Philipp Brandt, Carsten Lutz. International Joint Conference on Artificial Intelligence, 2005

1,298 citations recorded by the source corpus.

Recently, it has been shown that the small DL EL, which allows for conjunction and existential restrictions, has better algorithmic properties than its counterpart FL₀, which allows for conjunction and value restrictions. Whereas the subsumption problem in FL₀ becomes already intractable in the presence of aclyc 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 FL₀ with GCIs is EXPTIME-complete.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/eb7cfabee095cd9392ba2ff0f4d4ccfad0108427

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Hypertableau Reasoning for Description Logics (2009, methodology): “These reasoners, however, employ techniques that are quite dierent from the standard tableau algorithm; for example, on anEL++ ontology such as SNOMED CT, Pellet uses the reasoning algorithm by Baader, Brandt, and Lutz (2005) , and other reasoners employ specialized techniques as well (Haarslev, M”
Bridging the gap between OWL and relational databases (2007, background): “, DL-lite [9] or EL+ + [2]), provided that the “difficult” axioms are treated as constraints.”
OWL 2: The next step for OWL (2008, background): “scription logics, which have been designed to allow for efficient reasoning with large terminologies [1].”
Tractable Reasoning and Efficient Query Answering in Description Logics: The DL-Lite Family (2007, background): “In particular, in [4] it has been shown that for the basic language EL instance checking is polynomial even in the presence of general (i.”
Diagnosing Changes in An Ontology Stream: A DL Reasoning Approach (2012, methodology): “Indeed deciding both properties are depending on complexity of subsumption in EL++, which is PTIMEhard (Baader, Brandt, and Lutz 2005).”
Measuring Compositional Generalization: A Comprehensive Method on Realistic Data (2019, methodology): “For the internal logical form, we adopt a variation of the description logic EL (Baader et al., 2003; 2005), augmented with additional constructors (see Appendix I) to more easily map to certain linguistic structures.”
Computing the Least Common Subsumer w.r.t. a Background Terminology (2004, background): “Instead of extracting properties common to C 1 , . . . , C n , it just gives their disjunction, which does not provide us with new information.”
A general datalog-based framework for tractable query answering over ontologies (2009, background): “Guarded TGDs are sufficiently expressive to model the tractable description logic EL [10, 11] (as well as the more expressive ELI [62]; see Section 9.”
Taming the Infinite Chase: Query Answering under Expressive Relational Constraints (2008, background): “This formalism captures a wide variety of logics that so far were considered unrelated to each other: the OWL-based languages EL [6] and DL-Lite [27, 5] on the one hand and object-based languages like F-Logic Lite [23] on the other.”
Modular Reuse of Ontologies: Theory and Practice (2008, background): “EL ( Baader, Brandt, & Lutz, 2005 ) is a simple description logic which allows one to construct complex concepts using conjunction C1 u C2 and existential restriction 9R.C starting from atomic concepts A, roles R and the top concept >. EL provides no role constructors and no role axioms; thus, every”
Linking Data to Ontologies (2008, background): “Possible restrictions that guarantee polynomial reasoning have been studied and proposed in the context of description logics, such as Horn-SHIQ [17], EL [3], and DLP [12].”