ARAN - Access to Research at NUI Galway

Entailment for Domain-restricted RDF

ARAN - Access to Research at NUI Galway

Show simple item record

dc.contributor.author Polleres, Axel en
dc.date.accessioned 2009-11-30T10:29:47Z en
dc.date.available 2009-11-30T10:29:47Z en
dc.date.issued 2008 en
dc.identifier.citation Reinhard Pichler, Axel Polleres, Fang Wei, Stefan Woltran "Entailment for Domain-restricted RDF", Proceedings of the 5th European Semantic Web Conference (ESWC2008), Springer, 2008. en
dc.identifier.uri http://hdl.handle.net/10379/451 en
dc.description.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 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 prove that the entailment is tractable for unrestricted graphs and coNP-complete for domain-restricted graphs. en
dc.format application/pdf en
dc.language.iso en en
dc.publisher Springer en
dc.subject.lcsh Graph theory en
dc.title Entailment for Domain-restricted RDF en
dc.type Conference paper en
dc.local.publishedsource http://dx.doi.org/10.1007/978-3-540-68234-9 en
dc.local.publisherstatement The original publication is available at www.springerlink.com en
dc.description.peer-reviewed peer-reviewed en
dc.contributor.funder inContext en
dc.contributor.funder Science Foundation Ireland en

Files in this item

This item appears in the following Collection(s)

Show simple item record