W3C home > Mailing lists > Public > www-rdf-logic@w3.org > June 2004

Re: Can there be a decidable subset of OWL FULl?

From: Yuzhong Qu <yzqu@seu.edu.cn>
Date: Wed, 30 Jun 2004 18:04:27 +0800
Message-ID: <009e01c45e89$a11e1410$fd0b77ca@xobjects>
To: "Shengping Liu" <lsp@is.pku.edu.cn>
Cc: <www-rdf-logic@w3.org>
OWL DL is  a decidable subset of OWL FUL.

As to the reasoning complexity, 

OWL DL has a difficult entailment problem, as inference in SHOIN(D) is of worst-case nondeterministic exponential time (NExpTime) complexity.

Inference in SHIF(D) is of worst-case deterministic exponential time (ExpTime) complexity, and OWL Lite has the same complexity.


See below for some comment.


Yuzhong Qu 

Reference
[1] Ian Horrocks, Peter F. Patel-Schneider, and Frank van Harmelen. From SHIQ and RDF to OWL: The making of a web ontology language. Journal of Web Semantics, 1(1):7-26, 2003
[2] Stephan Tobies. Complexity Results and Practical Algorithms for Logics in Knowledge Representation. PhD thesis, LuFG Theoretical Computer Science, RWTHAachen,Germany, 2001.

----- Original Message ----- 
From: "Shengping Liu" <lsp@is.pku.edu.cn>
To: <www-rdf-logic@w3.org>
Sent: Tuesday, June 29, 2004 11:36 PM
Subject: Can there be a decidable subset of OWL FULl?



Hi,
  When trying to use OWL in real applications, Im in trouble: 
1) If I use OWL DL, most of constructs in RDF(S) cant be used, such as
statement about statement, class as instance. The corresponding RDF
become only a web-ized DL Abox language and arguably can be still called
RDF. We know that one design goals of RDF is "anyone can make statements
about any resource". But when using OWL DL, RDF loses its interesting
characters.
2)If I use OWL FULL, RDF(S) is okay, but reasoning in OWL full is
undecidable and there are no inference engine for OWL FULL.

I hope there can be a decidable subset of OWL FULL that is fully
compatible with  
RDF(S)(in syntax and semantics) and is more expressive than RDF Schema.
Since reasoning in RDF(S) is decidable, is there a conclusion that
RDF(S) is the most expressive and decidable language under the RDF
semantics?

* Haven't yet been proved. 
* Some Trade-off issues between expressiveness and decidablity. 

One application of the decidable subset of OWL Full is RDF Schema
mapping, for example, mapping a class in RDF Schema_A to an instance in
RDF Schema_B. 

* I see the situation. Context technique could be used in this kind of applications.

Thanks for any comments.

= = = = = = = = = = = = = = = = = = = = = = = = = = = =  
Shengping Liu(ƽ)
Department of Information Science, Peking University, China.
 
Phone: 86-10-62757175
Mail:  lsp@is.pku.edu.cn
 





Received on Wednesday, 30 June 2004 06:01:22 GMT

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