Show simple item record

dc.contributor.authorPolleres, Axelen
dc.date.accessioned2009-11-30T10:29:47Zen
dc.date.available2009-11-30T10:29:47Zen
dc.date.issued2008en
dc.identifier.citationReinhard 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.urihttp://hdl.handle.net/10379/451en
dc.description.abstractWe 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.formatapplication/pdfen
dc.language.isoenen
dc.publisherSpringeren
dc.subject.lcshGraph theoryen
dc.titleEntailment for Domain-restricted RDFen
dc.typeConference paperen
dc.local.publishedsourcehttp://dx.doi.org/10.1007/978-3-540-68234-9en
dc.local.publisherstatementThe original publication is available at www.springerlink.comen
dc.description.peer-reviewedpeer-revieweden
dc.contributor.funderinContexten
dc.contributor.funderScience Foundation Irelanden
nui.item.downloads341


Files in this item

Attribution-NonCommercial-NoDerivs 3.0 Ireland
This item is available under the Attribution-NonCommercial-NoDerivs 3.0 Ireland. No item may be reproduced for commercial purposes. Please refer to the publisher's URL where this is made available, or to notes contained in the item itself. Other terms may apply.

The following license files are associated with this item:

Thumbnail

This item appears in the following Collection(s)

Show simple item record