- From: Bijan Parsia <bparsia@isr.umd.edu>
- Date: Thu, 14 Apr 2005 10:40:09 -0400
- To: Enrico Franconi <franconi@inf.unibz.it>
- Cc: www-rdf-logic@w3.org, Paul Gearon <gearon@itee.uq.edu.au>
On Apr 14, 2005, at 10:28 AM, Enrico Franconi wrote: > On 10 Apr 2005, at 06:02, Bijan Parsia wrote: >> Remember that datalog's decision procedure is polynominal whereas OWL >> DL's is NEXPTIME and OWL Full is doesn't *have* a decision procedure >> (i.e., it's only semi-decidable). You ain't going to shoehorn the >> latter into the former without a trim...with a sledgehammer :) > > I like to be pedantic :-) Great! > Query answering in datalog is polynomial in data complexity (i.e., wrt > the dimension of the extensional DB), but it is EXPTIME-complete in > combined complexity (i.e., wrt the dimension of the whole knowledge > base). Ah, yes. I tend to forget that. > Instance checking in OWL-Lite is NP-complete (recent result by Boris > Motik) in data compexity, Interesting! Does he have a paper or tech report out on it? > while it is EXPTIME-complete in combined complexity. Instance checking > in OWL-DL is NEXPTIME-complete in combined complexity, but as far as I > know, the data complexity is still unknown. Interesting. > As a matter of fact, Boris just proposes to reduce SHIQ to > deterministic disjunctive datalog. Yes, and I've not before grasped how that was possible. Distinguishing the data complexity from the combined complexity is somewhat new to me (I first really go it from the DL-Lite papers), so I should revise my preconceptions across the board. Interesting! Cheers, Bijan Parsia.
Received on Thursday, 14 April 2005 14:40:11 UTC