- 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>
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 sheymans@vub.ac.be 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