[Back]

R. Pichler, St. Rümmele, S. Woltran:
"Belief Revision with Bounded Treewidth";
Talk: 10th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2009), Potsdam; 2009-09-14 - 2009-09-18; in: "Logic Programming and Nonmonotonic Reasoning", E. Erdem, F. Lin, T. Schaub (ed.); Springer, 5753 (2009), ISBN: 978-3-642-04237-9; 250 - 263.

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.

http://dx.doi.org/10.1007/978-3-642-04238-6

Project Head Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung