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

RE: AW: Datalog DEXPTIME Complexity + Safe Execution of Recursive Axioms + English

From: Lopatenko Andrei (A) <andrei.lopatenko@unibz.it>
Date: Tue, 7 Oct 2003 16:29:47 +0200
Message-ID: <97D017E3234BE745B37AD8C780E4DF53340E36@ubz02be.unibz.it>
To: "Adrian Walker" <adrianw@snet.net>, "Franconi Enrico (P)" <franconi@inf.unibz.it>
Cc: <www-rdf-logic@w3.org>, <www-rdf-interest@w3.org>

>inputs include variable datalog programs P.  So, the applicable
complexity 
>would appear to be "complete in DEXPTIME".

It means that generated datalog program should depend on not ontology
only, but also "A-box" or "database"?

Andrei Lopatenko
PhD student
The University of Manchester
Research Assistant
Free University of Bozen-Bolzano
tel. 39(+0471)315-644


Program complexity is the complexity of checking whether Din U P |= A
for 
variable datalog programs P and ground atoms A over a fixed input
database 
Din.  It is complete in DEXPTIME.

Now it would seem that, if one is proposing a rule interpreter, then its

inputs include variable datalog programs P.  So, the applicable
complexity 
would appear to be "complete in DEXPTIME".

What do you think ?

                         Cheers --    Adrian



                                        INTERNET BUSINESS LOGIC

Business Rules in English + Semantic Data Integration + Your Oracle
Databases

                                           www.reengineeringllc.com

Adrian Walker
Reengineering LLC
PO Box 1412
Bristol
CT 06011-1412 USA

Phone: USA 860 583 9677
Cell:    USA  860 830 2085
Fax:    USA  860 314 1029
Received on Tuesday, 7 October 2003 10:30:36 GMT

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