- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Fri, 15 Apr 2005 10:01:23 +0200
- To: Bijan Parsia <bparsia@isr.umd.edu>
- Cc: www-rdf-logic@w3.org, Paul Gearon <gearon@itee.uq.edu.au>
On 14 Apr 2005, at 16:40, Bijan Parsia wrote: > On Apr 14, 2005, at 10:28 AM, Enrico Franconi wrote: >> 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? It can be understood as a corollary of his KR'04 paper - even if he did not realise it at first. As such, I believe that the explicit result is still unpublished. In short. NP-hardness in data complexity of instance checking for ALC was already known (folklore since Andrea Schaerf's PhD thesis in the early 90ies). Boris proves a reduction of instance checking of SHIQ in deterministic disjunctive datalog, which is NP-complete in data complexity; this proves the upper bound. Hence, instance checking is NP-complete in data complexity for ALC, SHIQ, OWL-Lite. cheers --e.
Received on Friday, 15 April 2005 08:01:30 UTC