@inproceedings{pich-etal-2008,
	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 prove that the entailment is tractable for unrestricted graphs and coNP-complete for domain-restricted graphs. 
},
	Address = {Tenerife, Spain},
	Author = {Reinhard Pichler and Axel Polleres and Fang Wei and Stefan Woltran},
	Booktitle = {Proceedings of the 5th European Semantic Web Conference (ESWC2008)},
	Day = {1-5},
	Month = JUN,
	Pages = {200--214},
	Projects = {incontext,lion},
	Publisher = {Springer},
	Series = LNCS,
	Talk = {Axel Polleres},
	Title = {Entailment for Domain-restricted {RDF}},
	Type = CONF,
	Url = {http://www.polleres.net/publications/pich-etal-2008.pdf},
	Volume = 5021,
	Year = 2008,
	Bdsk-Url-1 = {http://www.polleres.net/publications/pich-etal-2008.pdf}}

{"_id":"4XLgmTr2TfruaTorJ","bibbaseid":"pichler-polleres-wei-woltran-entailmentfordomainrestrictedrdf-2008","downloads":0,"creationDate":"2015-12-16T06:35:18.000Z","title":"Entailment for Domain-restricted RDF","author_short":["Pichler, R.","Polleres, A.","Wei, F.","Woltran, S."],"year":2008,"bibtype":"inproceedings","biburl":"www.polleres.net/mypublications.bib","bibdata":{"bibtype":"inproceedings","type":"Conference paper","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. ","address":"Tenerife, Spain","author":[{"firstnames":["Reinhard"],"propositions":[],"lastnames":["Pichler"],"suffixes":[]},{"firstnames":["Axel"],"propositions":[],"lastnames":["Polleres"],"suffixes":[]},{"firstnames":["Fang"],"propositions":[],"lastnames":["Wei"],"suffixes":[]},{"firstnames":["Stefan"],"propositions":[],"lastnames":["Woltran"],"suffixes":[]}],"booktitle":"Proceedings of the 5th European Semantic Web Conference (ESWC2008)","day":"1-5","month":"June","pages":"200–214","projects":"incontext,lion","publisher":"Springer","series":"Lecture Notes in Computer Science (LNCS)","talk":"Axel Polleres","title":"Entailment for Domain-restricted RDF","url":"http://www.polleres.net/publications/pich-etal-2008.pdf","volume":"5021","year":"2008","bdsk-url-1":"http://www.polleres.net/publications/pich-etal-2008.pdf","bibtex":"@inproceedings{pich-etal-2008,\n\tAbstract = {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 prove that the entailment is tractable for unrestricted graphs and coNP-complete for domain-restricted graphs. \n},\n\tAddress = {Tenerife, Spain},\n\tAuthor = {Reinhard Pichler and Axel Polleres and Fang Wei and Stefan Woltran},\n\tBooktitle = {Proceedings of the 5th European Semantic Web Conference (ESWC2008)},\n\tDay = {1-5},\n\tMonth = JUN,\n\tPages = {200--214},\n\tProjects = {incontext,lion},\n\tPublisher = {Springer},\n\tSeries = LNCS,\n\tTalk = {Axel Polleres},\n\tTitle = {Entailment for Domain-restricted {RDF}},\n\tType = CONF,\n\tUrl = {http://www.polleres.net/publications/pich-etal-2008.pdf},\n\tVolume = 5021,\n\tYear = 2008,\n\tBdsk-Url-1 = {http://www.polleres.net/publications/pich-etal-2008.pdf}}\n\n","author_short":["Pichler, R.","Polleres, A.","Wei, F.","Woltran, S."],"key":"pich-etal-2008","id":"pich-etal-2008","bibbaseid":"pichler-polleres-wei-woltran-entailmentfordomainrestrictedrdf-2008","role":"author","urls":{"Paper":"http://www.polleres.net/publications/pich-etal-2008.pdf"},"metadata":{"authorlinks":{"polleres, a":"https://bibbase.org/show?bib=www.polleres.net/mypublications.bib"}}},"search_terms":["entailment","domain","restricted","rdf","pichler","polleres","wei","woltran"],"keywords":[],"authorIDs":["FyLDFGg993nDS2Spf"],"dataSources":["cBfwyqsLFQQMc4Fss","gixxkiKt6rtWGoKSh","QfLT6siHZuHw9MqvK"]}