[Back]


Talks and Poster Presentations (with Proceedings-Entry):

S. Woltran:
"Belief Revision with Bounded Treewidth";
Talk: Dagstuhl Seminar 09351: Information processing, rational belief change and social interaction, Wadern, Schloss Dagstuhl, Deutschland (invited); 08-23-2009 - 08-27-2009; in: "Dagstuhl Seminar Proceedings", G. Bonanno, J. Delgrande, H. Rott (ed.); (2009), ISSN: 1862-4405; 51 pages.



English 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 talk, we present such tractable fragments exploiting the
notion of treewidth. More specifically, we present a new algorithm
based on dynamic programming for problems in Dalal's setting and a
tractability proof using Courcelle's Theorem for Satoh's approach.

Created from the Publication Database of the Vienna University of Technology.