W3C home > Mailing lists > Public > www-rdf-interest@w3.org > October 2003

Re: Safe Execution of Recursive Axioms + English

From: Enrico Franconi <franconi@inf.unibz.it>
Date: Thu, 2 Oct 2003 00:19:26 +0200
Cc: Tanel Tammet <tammet@staff.ttu.ee>, rdf-logic@w3.org, www-rdf-interest@w3.org
To: Adrian Walker <adrianw@snet.net>
Message-Id: <514BEF7F-F45D-11D7-B4E7-000A9575BDDE@inf.unibz.it>

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 GMT

This archive was generated by hypermail 2.2.0+W3C-0.50 : Monday, 7 December 2009 10:52:02 GMT