[DL] question about the description logic EL

Diego Calvanese calvanese at inf.unibz.it
Fri May 9 11:22:06 CEST 2008

EL allows for qualified existential quantification.
As such it is a separate logic from AL.  Notice that reasoning over  
EL TBoxes with arbitrary (possibly cyclic) GCIs is polynomial (even  
with additional constructs), while this is not the case for AL, for  
which the same problem is EXPTIME-complete.

There has been a lot of work around EL recently, including work on  
conjunctive query answering.  See, e.g.,

Franz Baader, Sebastian Brandt, Carsten Lutz: Pushing the EL  
Envelope. IJCAI 2005: 364-369
Franz Baader, Carsten Lutz, Boontawee Suntisrivaraporn: CEL - A  
Polynomial-Time Reasoner for Life Science Ontologies. IJCAR 2006:  
Riccardo Rosat: On conjunctive query answering in EL.  DL 2007
Adila Krisnadhi, Carsten Lutz: Data Complexity in the EL Family of  
Description Logics. LPAR 2007: 333-347

- Diego

On 6 May 2008, at 21:50, Yvonne Violet Shashoua wrote:
>    I was reading the Description Logic Handbook, and in the  
> appendix, on page 535, they mention the description logic EL, which  
> they say allows intersection of concepts and existential  
> quantification.  But it is not clear to me from the context whether  
> they mean only limited existential quantification (where the only  
> role allowed after the dot is TRUE) or full existential  
> quantification.  This affects whether EL is a restriction of AL or  
> a completely separate description logic.  I would love some help  
> with understanding this.  Thanks.
> ---
> **  You received this mail via the description logic mailing list;  
> for more  **
> **  information, visit the description logic homepage at http:// 
> dl.kr.org/.  **

Diego Calvanese
Faculty of Computer Science         e-mail: calvanese at inf.unibz.it
Free University of Bozen-Bolzano    phone: +39-0471 016 160
Piazza Domenicani 3                 fax:   +39-0471 016 009
I-39100 Bolzano-Bozen BZ, Italy     http://www.inf.unibz.it/~calvanese/

More information about the dl mailing list