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

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

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