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)
|