<div class="csl-bib-body">
<div class="csl-entry">Pichler, R., Rümmele, S., & Woltran, S. (2009). Belief Revision with Bounded Treewidth. In E. Erdem, F. Lin, & T. Schaub (Eds.), <i>Logic Programming and Nonmonotonic Reasoning: 10th International Conference, LPNMR 2009, Potsdam, Germany, September 14-18, 2009, Proceedings</i> (pp. 250–263). Springer. https://doi.org/10.1007/978-3-642-04238-6_22</div>
</div>
-
dc.identifier.isbn
9783642042379
-
dc.identifier.isbn
9783642042386
-
dc.identifier.uri
http://hdl.handle.net/20.500.12708/52759
-
dc.description.abstract
Problems arising from the revision of propositional knowledge bases
have been intensively studied for two decades. Many different approaches to revision have thus been suggested, with the ones by Dalal or Satoh being two of the most fundamental ones. As is well known, most computational tasks in this area are intractable. Therefore, in practical applications, one requires sufficient
conditions under which revision problems become efficiently solvable. In this paper, we identify such tractable fragments for the reasoning and the enumeration problem exploiting the notion of treewidth. More specifically, we present new algorithms based on dynamic programming for these problems in Dalal´s setting and a tractability proof using Courcelle´s Theorem for Satoh´s approach.
en
dc.description.sponsorship
Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
-
dc.language.iso
en
-
dc.publisher
Springer
-
dc.relation.ispartofseries
Lecture Notes in Computer Science
-
dc.title
Belief Revision with Bounded Treewidth
en
dc.type
Konferenzbeitrag
de
dc.type
Inproceedings
en
dc.relation.isbn
978-3-642-04237-9
-
dc.relation.doi
10.1007/978-3-642-04238-6
-
dc.relation.issn
0302-9743
-
dc.description.startpage
250
-
dc.description.endpage
263
-
dc.type.category
Full-Paper Contribution
-
dc.relation.eissn
1611-3349
-
dc.publisher.place
5753
-
tuw.booktitle
Logic Programming and Nonmonotonic Reasoning: 10th International Conference, LPNMR 2009, Potsdam, Germany, September 14-18, 2009, Proceedings
-
tuw.peerreviewed
true
-
tuw.relation.publisher
Springer
-
tuw.relation.publisherplace
Berlin, Heidelberg
-
tuw.project.title
Theoretical Tractability vs. Practical Computation
-
tuw.researchTopic.id
C5
-
tuw.researchTopic.name
Computer Science Foundations
-
tuw.researchTopic.value
100
-
tuw.publication.orgunit
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
tuw.publisher.doi
10.1007/978-3-642-04238-6_22
-
dc.description.numberOfPages
14
-
tuw.event.name
10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009)
-
tuw.event.startdate
14-09-2009
-
tuw.event.enddate
18-09-2009
-
tuw.event.online
On Site
-
tuw.event.type
Event for scientific audience
-
tuw.event.place
Potsdam, Germany
-
tuw.event.place
Potsdam, Germany
-
tuw.event.country
EU
-
tuw.event.presenter
Woltran, Stefan
-
wb.sciencebranch
Mathematik, Informatik
-
wb.sciencebranch.oefos
11
-
wb.presentation.type
science to science/art to art
-
item.fulltext
no Fulltext
-
item.cerifentitytype
Publications
-
item.openairecristype
http://purl.org/coar/resource_type/c_5794
-
item.languageiso639-1
en
-
item.openairetype
conference paper
-
item.grantfulltext
none
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.dept
E184 - Institut für Informationssysteme
-
crisitem.author.dept
E192-02 - Forschungsbereich Databases and Artificial Intelligence
-
crisitem.author.orcid
0000-0002-1760-122X
-
crisitem.author.orcid
0000-0003-1594-8972
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.author.parentorg
E180 - Fakultät für Informatik
-
crisitem.author.parentorg
E192 - Institut für Logic and Computation
-
crisitem.project.funder
FWF Fonds zur Förderung der wissenschaftlichen Forschung (FWF)