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

AW: AW: Safe Execution of Recursive Axioms + English

From: Raphael Volz <volz@aifb.uni-karlsruhe.de>
Date: Tue, 7 Oct 2003 14:50:21 +0200
To: "Enrico Franconi" <franconi@inf.unibz.it>, "Raphael Volz" <rvo@aifb.uni-karlsruhe.de>
Cc: <www-rdf-logic@w3.org>, "Boris Motik" <motik@fzi.de>
Message-ID: <CJEPKBAAMOMMFPDCDFGFAEJPDNAA.volz@aifb.uni-karlsruhe.de>


> > I would like to stay with my belief, you may choose to do some
> > preprocessing and compile things and later use your polynomial language
> > to do the rest.
>
> I don't get your point. A proof is stronger than a belief :-)

I got your point, no one says that what the preprocessor does necessarily
has to be tractable.

>
> > > > What you seems to be possible
> > > > is using Disjunctive Logic Programs, but our proof that an
> > > > appropriate translation is indeed correct is not quite finished
> > > > yet. Empirically, we pass all tests in the OWL Test Suite and
> > > > other well-known DL tests.
> > >
> > > Still, DLP in its full power is below PSPACE, so again no
> reasonable DL

Of course, the data complextity of DLP is Sgima-Pi-2, so it is still in the
polynomial hierarchy, but it is Nexptime^NP-complete in the program size. We
a working on a
reduction of SHIQ to Disj. Datalog with equality, (w/o closed world negation
!)
which will for some knowledge base generate a set of rules (whose number is
worst-case exponential in the size of the knowledge base), which preserves
satisfiabilty and entailment. You may contact Boris (motik@fzi.de) to ask
further questions and/or
take his proof apart.

Sincerely yours

R.
Received on Tuesday, 7 October 2003 08:50:34 GMT

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