ontology-summit
[Top] [All Lists]

[ontology-summit] FW: Question on DL negation [DL complexity tool]

To: "Ontology Summit 2007 Forum" <ontology-summit@xxxxxxxxxxxxxxxx>
From: "Obrst, Leo J." <lobrst@xxxxxxxxx>
Date: Mon, 5 Mar 2007 11:59:21 -0500
Message-id: <9F771CF826DE9A42B548A08D90EDEA8001AB128B@xxxxxxxxxxxxxxxxx>

FYI. This is a useful tool for determining the specific complexity of
the description logic you are interested in.    (01)

Leo     (02)


_____________________________________________ 
Dr. Leo Obrst       The MITRE Corporation, Information Semantics 
lobrst@xxxxxxxxx    Center for Innovative Computing & Informatics 
Voice: 703-983-6770 7515 Colshire Drive, M/S H305 
Fax: 703-983-1379   McLean, VA 22102-7508, USA     (03)


-----Original Message-----
From: public-owl-dev-request@xxxxxx
[mailto:public-owl-dev-request@xxxxxx] On Behalf Of Bijan Parsia
Sent: Monday, March 05, 2007 11:37 AM
To: Michael Schneider
Cc: matthew.williams@xxxxxxxxxxxxx; semantic-web@xxxxxx;
public-owl-dev@xxxxxx
Subject: Re: Question on DL negation    (04)


In addition to Uli's wise words, I, as usual, recommend the  
description logic complexity navigator:
        http://www.cs.man.ac.uk/~ezolin/logic/complexity.html    (05)

You can see by playing around with combinations of the role  
constructors the effects on complexity.    (06)

Remember that all this is just (a fragment of) FOL (well, except if  
you add transitive closure per se), so all the constructors are just  
normal propositional (for the most part) connectives on binary  
predicates.    (07)

Expressive role constructors are associated with propositional  
dynamic logic (and converse propositional dynamic logic).    (08)

It's also instructive to see how arbitrary concept negation is  
difficult. You can see in the tractable fragments document that most  
of them allow concept (i.e., restricted) disjointness:
        <http://www.cs.man.ac.uk/~ezolin/logic/complexity.html>    (09)

Lots of recent work (e.g., on modularity, the EL family, and ABox  
summarization) suggests strongly that unrestricted universal  
quantification and negation make things difficult. If you can control  
them in a number of ways (either by analysis or by linguistic  
restrictions) you can get better behavior.    (010)

Cheers,
Bijan.    (011)


_________________________________________________________________
Msg Archives: http://ontolog.cim3.net/forum/ontology-summit/ 
Subscribe/Config: http://ontolog.cim3.net/mailman/listinfo/ontology-summit/  
Unsubscribe: mailto:ontology-summit-leave@xxxxxxxxxxxxxxxx
Community Files: http://ontolog.cim3.net/file/work/OntologySummit2007/
Community Wiki: http://ontolog.cim3.net/cgi-bin/wiki.pl?OntologySummit2007
Community Portal: http://ontolog.cim3.net/    (012)
<Prev in Thread] Current Thread [Next in Thread>