Qucosa (Saxon State and University Library Dresden) · 2005 · 863 citations · 19 references
Open access
The EL description logic, which supports conjunction and existential restrictions, has tractable subsumption even with general concept inclusion axioms, unlike FL0 where subsumption becomes intractable with acyclic TBoxes. The study aims to identify expressive extensions to EL that preserve tractability. The authors extend EL by adding a set of expressive constructors while analyzing their impact on subsumption tractability. They find that most additional DL constructors render subsumption intractable, often EXPTIME‑complete, and that FL0 with GCIs is also EXPTIME‑complete.
Recently, it has been shown that the small description logic (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 with general concept inclusion axioms (GCIs). On the one hand, we 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 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 show that subsumption in FL0 with GCIs is EXPTIME-complete.
19
Gene Ontology: tool for the unification of biology
Michael Ashburner, Catherine A. Ball, Judith A. Blake et al. · Nature Genetics · 2000 · 43.3K citations · Full text
Functional Genomics, Engineering, Bioinformatics Database +11
Using an Expressive Description Logic: FaCT or Fiction?
Ian Horrocks · 1998 · 396 citations