Sufficient and necessary conditions for Dynamic Programming in
  Valuation-Based Systems
  Valuation algebras abstract a large number of formalisms for automated
reasoning and enable the definition of generic inference procedures. Many of
these formalisms provide some notion of solution. Typical examples are
satisfying assignments in constraint systems, models in logics or solutions to
linear equation systems.
  Many widely used dynamic programming algorithms for optimization problems
rely on low treewidth decompositions and can be understood as particular cases
of a single algorithmic scheme for finding solutions in a valuation algebra.
The most encompassing description of this algorithmic scheme to date has been
proposed by Pouly and Kohlas together with sufficient conditions for its
correctness. Unfortunately, the formalization relies on a theorem for which we
provide counterexamples. In spite of that, the mainline of Pouly and Kohlas'
theory is correct, although some of the necessary conditions have to be
revised. In this paper we analyze the impact that the counter-examples have on
the theory, and rebuild the theory providing correct sufficient conditions for
the algorithms. Furthermore, we also provide necessary conditions for the
algorithms, allowing for a sharper characterization of when the algorithmic
scheme can be applied.
