Binary moment diagram


A binary moment diagram is a generalization of the binary decision diagram to linear functions over domains such as booleans, but also to integers or to real numbers.
They can deal with boolean functions with complexity comparable to BDDs, but also some functions that are dealt with very inefficiently in a BDD are handled easily by BMD, most notably multiplication.
The most important properties of BMD is that, like with BDDs, each function has exactly one canonical representation, and many operations can be efficiently performed on these representations.
The main features that differentiate BMDs from BDDs are using linear instead of pointwise diagrams, and having weighted edges.
The rules that ensure the canonicity of the representation are:
In pointwise decomposition, like in BDDs, on each branch point we store result of all branches separately. An example of such decomposition for an integer function is:
In linear decomposition we provide instead a default value and a difference:
It can easily be seen that the latter representation is much more efficient in case of additive functions, as when we add many elements the latter representation will have only O elements, while the former, even with sharing, exponentially many.

Edge weights

Another extension is using weights for edges. A value of function at given node is a sum of the true nodes below it times the edges' weights.
For example, can be represented as:
  1. Result node, always 1× value of node 2, if add 4× value of node 4
  2. Always 1× value of node 3, if add 2× value of node 4
  3. Always 0, if add 1× value of node 4
  4. Always 1× value of node 5, if add +4
  5. Always 1× value of node 6, if add +2
  6. Always 0, if add +1
Without weighted nodes a much more complex representation would be required:
  1. Result node, always value of node 2, if value of node 4
  2. Always value of node 3, if value of node 7
  3. Always 0, if value of node 10
  4. Always value of node 5, if add +16
  5. Always value of node 6, if add +8
  6. Always 0, if add +4
  7. Always value of node 8, if add +8
  8. Always value of node 9, if add +4
  9. Always 0, if add +2
  10. Always value of node 11, if add +4
  11. Always value of node 12, if add +2
  12. Always 0, if add +1