Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary

@article{citeulike:1019435, abstract = {We prove that entailment for RDF Schema (RDFS) is decidable, NP-complete, and in P if the target graph does not contain blank nodes. We show that the standard set of entailment rules for RDFS is incomplete and that this can be corrected by allowing blank nodes in predicate position.We define semantic extensions of RDFS that involve datatypes and a subset of the OWL vocabulary that includes the property-related vocabulary (e.g. FunctionalProperty), the comparisons (e.g. sameAs and differentFrom) and the value restrictions (e.g. allValuesFrom). These semantic extensions are in line with the `if-semantics' of RDFS and weaker than the `iff-semantics' of D-entailment and OWL (DL or Full). For these semantic extensions we present entailment rules, prove completeness results, prove that consistency is in P and that, just as for RDFS, entailment is NP-complete, and in P if the target graph does not contain blank nodes. There are no restrictions on use to obtain decidability: classes can be used as instances.}, author = {Herman}, booktitle = {Selcted Papers from the International Semantic Web Conference, 2004 - ISWC, 2004}, citeulike-article-id = {1019435}, doi = {http://dx.doi.org/10.1016/j.websem.2005.06.001}, journal = {Web Semantics: Science, Services and Agents on the World Wide Web}, keywords = {reasoning}, month = {October}, number = {2-3}, pages = {79--115}, posted-at = {2007-06-14 17:33:49}, priority = {2}, title = {Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary}, url = {http://dx.doi.org/10.1016/j.websem.2005.06.001}, volume = {3}, year = {2005} }

TY - JOUR ID - citeulike:1019435 L3 - citeulike-article-id:1019435 TI - Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary T2 - Selcted Papers from the International Semantic Web Conference, 2004 - ISWC, 2004 JF - Web Semantics: Science, Services and Agents on the World Wide Web VL - 3 IS - 2-3 SP - 79 EP - 115 N2 - We prove that entailment for RDF Schema (RDFS) is decidable, NP-complete, and in P if the target graph does not contain blank nodes. We show that the standard set of entailment rules for RDFS is incomplete and that this can be corrected by allowing blank nodes in predicate position.We define semantic extensions of RDFS that involve datatypes and a subset of the OWL vocabulary that includes the property-related vocabulary (e.g. FunctionalProperty), the comparisons (e.g. sameAs and differentFrom) and the value restrictions (e.g. allValuesFrom). These semantic extensions are in line with the `if-semantics' of RDFS and weaker than the `iff-semantics' of D-entailment and OWL (DL or Full). For these semantic extensions we present entailment rules, prove completeness results, prove that consistency is in P and that, just as for RDFS, entailment is NP-complete, and in P if the target graph does not contain blank nodes. There are no restrictions on use to obtain decidability: classes can be used as instances. KW - reasoning AU - Herman PY - 2005/10// UR - http://dx.doi.org/10.1016/j.websem.2005.06.001 ER -