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

Re: AW: AW: Safe Execution of Recursive Axioms + English

From: Stijn Heymans <sheymans@vub.ac.be>
Date: Wed, 8 Oct 2003 13:04:49 +0200 (CEST)
To: Raphael Volz <volz@aifb.uni-karlsruhe.de>
Cc: Enrico Franconi <franconi@inf.unibz.it>, Raphael Volz <rvo@aifb.uni-karlsruhe.de>, <www-rdf-logic@w3.org>, Boris Motik <motik@fzi.de>
Message-ID: <Pine.LNX.4.33.0310081257530.29799-100000@tinf1.vub.ac.be>

On Tue, 7 Oct 2003 at 14:50, Raphael Volz wrote:

> 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.

In [1] (and earlier on in [2]), available at
http://tinf2.vub.ac.be/~sheymans/publications/, we provide a reduction
from SHIQ to a restricted form of Disjunctive logic programs (DLPs) with inequality and
additionally open domains.

The (syntactic) restrictions on DLP make sure that reasoning with ineq.
and open domains remains decidable. In our case we allow only rules that
have a tree-structure, and we called the DLPs free tree DLPs - or
FTDLPs. Just extending DLP with inequality
and open domains (possibly with constraint rules, which are rules with
empty head) makes satisfiability checking undecidable.

Furthermore, reasoning with such FTDLPs takes exponential time (as it
should since it can simulate the DL SHIQ).

Best Regards,
Stijn Heymans

[1] Integrating Semantic Web Reasoning and Answer Set
	Programming. Answer Set Programming: Advances in Theory and
	Implementation (ASP03).  September, 2003. Messina, Sicily.

[2] Integrating Ontology Languages and Answer Set Programming.
	Second International Workshop on Web Semantics - WebS (at DEXA 2003).
	September, 2003.  Prague, Czech Republic.

Stijn Heymans
Dept. of Computer Science, DINF 10G721
Vrije Universiteit Brussel, VUB
Pleinlaan 2
B1050 Brussels, Belgium
Received on Wednesday, 8 October 2003 07:21:01 UTC

This archive was generated by hypermail 2.3.1 : Wednesday, 2 March 2016 11:10:40 UTC