Re: Safe Execution of Recursive Axioms + English

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 Thursday, 2 October 2003 02:23:50 UTC