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

Re: rdf(s) decidablity?

From: Peter F. Patel-Schneider <pfps@research.bell-labs.com>
Date: Thu, 04 Dec 2003 12:42:31 -0500 (EST)
Message-Id: <20031204.124231.64991183.pfps@research.bell-labs.com>
To: lsp@is.pku.edu.cn
Cc: www-rdf-logic@w3.org

From: "lsp" <lsp@is.pku.edu.cn>
Subject: rdf(s) decidablity?
Date: Fri, 5 Dec 2003 01:20:47 +0800

> In [1] section 3.1: 
>    "although RDFS seems to be a very simple language (much too simple
> for many Semantic Web applications), its transformation into FOL is not
> included in any of the above mentioned decidable fragments."
>  
> Is this mean that RDFS is undecidable? Is there any formal proof?
>  
> As regards to RDF Model Theory, is there any complexity results about
> rdfs entailment?
>  
> Thanks!
>  
> Liu shengping
>  
> [1] Ian Horrocks, Peter F. Patel-Schneider , Three Theses of
> Representation in the Semantic Web, WWW2003.

Entailment in RDF and RDFS is decidable, although I do not believe that
there is a direct proof of this in the RDF documents.  However, if you
transform RDFS into FOL you end up using a lot of the power of FOL.

As far as complexity of reasoning in RDFS goes, I'm not aware of any formal
results in this area, but I haven't been looking for anything in this
area.   


Peter F. Patel-Schneider
Received on Thursday, 4 December 2003 12:43:02 GMT

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