- From: Enrico Franconi <franconi@inf.unibz.it>
- Date: Thu, 2 Oct 2003 00:19:26 +0200
- To: Adrian Walker <adrianw@snet.net>
- Cc: Tanel Tammet <tammet@staff.ttu.ee>, rdf-logic@w3.org, www-rdf-interest@w3.org
On Wednesday, Oct 1, 2003, at 20:14 Europe/Rome, Adrian Walker wrote: > The Internet Business Logic engine capabilities mentioned below are > stratified datalog with negation, plus some aggregation operations > (SDA). It's possible that this goes beyond polynomial complexity. > For the purposes of exploring Tamel's questions, it may turn out that > SDA is enough. > But for more general purposes, can you point me to the proof that OWL > is EXPTIME-hard please? I don't think that aggregation has been used in this context capture, for example, even the complexity of the propositional content of OWL (which is obviously a NP-hard component). The EXPTIME-hardness complexity comes from the fact that it is possible to encode in OWL-dl and OWL-lite the simplest propositionally complete description logic (i.e., ALC) which is EXPTIME-complete. cheers --e. Enrico Franconi - franconi@inf.unibz.it Free University of Bozen-Bolzano - http://www.inf.unibz.it/~franconi/ Faculty of Computer Science - Phone: (+39) 0471-315-642 I-39100 Bozen-Bolzano BZ, Italy - Fax: (+39) 0471-315-649 On Wednesday, Oct 1, 2003, at 18:44 Europe/Rome, Enrico Franconi wrote: > This is soemthing I always wanted to ask: how comes that reasoning for > a language like OWL (starting from OWL-lite itself) -- whose > complexity has been proved to be EXPTIME-hard -- is going to be > implemented with a polynomial language such as the datalog variant > you're talking about? I've seen many implementations based on this > idea (e.g., based on ECA rules), and I wonder whether there is > something I'm missing.
Received on Wednesday, 1 October 2003 18:19:29 UTC