BibSonomy :: publication ::

tag user group author concept BibTeX key search:all search:eswc2008

The blue social bookmark and publication sharing system.

entry of eswc2008:

(0)

This publication has not been reviewed yet.

rating distribution

average user rating

The average rating is computed over all reviews. However, some of them may be invisible to you due to the visibility setting chosen by the reviewers.

(0.0 of 5.0 based on 0 reviews)

Entailment for Domain-restricted RDF

by: Reinhard Pichler, Axel Polleres, Fang Wei, and Stefan Woltran

In: Proceedings of the 5th European Semantic Web Conference Berlin, Heidelberg: Springer Verlag (June 2008) .

Resources (URL, PDF, PS...)

URL:	http://data.semanticweb.org/conference/eswc/2008/papers/120

We introduce domain-restricted RDF dRDF which allows to associate an RDF graph with a fixed, finite domain that interpretations for it may range over. We show that dRDF is a real extension of RDF and discuss impacts on the complexity of entailment in dRDF. The entailment problem represents the key reasoning task for RDF and is well known to be NP-complete. Remarkably, we show that the restriction of domains in dRDF raises the complexity of entailment from NP- to $\Pi^P_2$-completeness. In order to lower complexity of entailment for both domain-restricted and unrestricted graphs, we take a closer look at the graph structure. For cases where the structure of RDF graphs is restricted via the concept of bounded treewidth, we manage to prove tractability of entailment. We also present a polynomial entailment checking algorithm for such graphs.

BibTeX record

@inproceedings{pichler2008entailment,
  abstract = {We introduce domain-restricted RDF (dRDF) which allows to associate an RDF graph with a fixed, finite domain that interpretations for it may range over. We show that dRDF is a real extension of RDF and discuss impacts on the complexity of entailment in dRDF. The entailment problem represents the key reasoning task for RDF and is well known to be NP-complete. Remarkably, we show that the restriction of domains in dRDF raises the complexity of entailment from NP- to $\Pi^P_2$-completeness. In order to lower complexity of entailment for both domain-restricted and unrestricted graphs, we take a closer look at the graph structure. For cases where the structure of RDF graphs is restricted via the concept of bounded treewidth, we manage to prove tractability of entailment. We also present a polynomial entailment checking algorithm for such graphs.},
  added-at = {2008-05-28T14:49:57.000+0200},
  address = {Berlin, Heidelberg},
  author = {Pichler, Reinhard and Polleres, Axel and Wei, Fang and Woltran, Stefan},
  biburl = {http://www.bibsonomy.org/bibtex/254b3e29ce6a6f65fd0cd595a0904f919/eswc2008},
  booktitle = {Proceedings of the 5th European Semantic Web Conference},
  editor = {Hauswirth, Manfred and Koubarakis, Manolis and Bechhofer, Sean},
  interhash = {ad4c325731fe9bee1eac3f75252c127f},
  intrahash = {54b3e29ce6a6f65fd0cd595a0904f919},
  keywords = {rdf semantic h-subsumption web entailment complexity formal-languages-2},
  month = {June},
  publisher = {Springer Verlag},
  series = {LNCS},
  timestamp = {2008-05-28T14:49:57.000+0200},
  title = {Entailment for Domain-restricted RDF},
  url = {http://data.semanticweb.org/conference/eswc/2008/papers/120},
  year = 2008
}

Endnote record

%0 Conference Paper
%1 pichler2008entailment
%A Pichler, Reinhard
%A Polleres, Axel
%A Wei, Fang
%A Woltran, Stefan
%B Proceedings of the 5th European Semantic Web Conference
%C Berlin, Heidelberg
%D 2008
%E Hauswirth, Manfred
%E Koubarakis, Manolis
%E Bechhofer, Sean
%I Springer Verlag
%K 
%T Entailment for Domain-restricted RDF
%U http://data.semanticweb.org/conference/eswc/2008/papers/120
%X We introduce domain-restricted RDF (dRDF) which allows to associate an RDF graph with a fixed, finite domain that interpretations for it may range over. We show that dRDF is a real extension of RDF and discuss impacts on the complexity of entailment in dRDF. The entailment problem represents the key reasoning task for RDF and is well known to be NP-complete. Remarkably, we show that the restriction of domains in dRDF raises the complexity of entailment from NP- to $\Pi^P_2$-completeness. In order to lower complexity of entailment for both domain-restricted and unrestricted graphs, we take a closer look at the graph structure. For cases where the structure of RDF graphs is restricted via the concept of bounded treewidth, we manage to prove tractability of entailment. We also present a polynomial entailment checking algorithm for such graphs.

BibSonomy :: publication ::

Entailment for Domain-restricted RDF

Resources (URL, PDF, PS...)

Abstract

BibTeX record

Endnote record