BMD, Datenstruktur für Funktionen \(f:{\{0,1\}}^{n}\to {\mathbb{Z}}\). Der Aufbau eines BMD entspricht dem eines binären Entscheidungsgraphen mit dem Unterschied, daß die Blätter mit ganzen Zahlen und nicht nur mit den Werten 0 und 1 markiert sind.

Ist jeder Kante e noch zusätzlich ein Gewicht c_eaus \({\mathbb{Z}}\) zugeordnet, so spricht man von multiplicative binary moment diagram oder *BMD. Ein BMD kann als *BMD aufgefaßt werden, bei dem alle Kantengewichte gleich 1 sind.

Ein *BMD mit Wurzel w, der über der n-elementigen Variablenmenge {x₁,…,x_n} definiert ist, beschreibt eine Funktion \({f}_{w}:{\{0,1\}}^{n}\to {\mathbb{Z}}\), definiert wie folgt:

1. Ist w ein Blatt, \(index(W)\in {\mathbb{Z}}\) die Markierung von w, so ist f_w die konstante Abbildung, die jedes Argument auf den Wert index(w) abbildet.
2. Ist w ein innerer Knoten und index(w) = x_i, so ist

   \begin{eqnarray}{f}_{w} & = & {c}_{(w,low(w))}\cdot {f}_{low(w)}\\ & & +{x}_{i}\cdot {c}_{(w,high(w))}\cdot {f}_{high(w)}.\end{eqnarray}

   *BMDs sind unter bestimmten Einschränkungen kanonische Darstellungen der Funktionen \(f:{\{0,1\}}^{n}\to {\mathbb{Z}}\). Sie müssen geordnet (geordneter binärer Entscheidungsgraph) sein, und die multiplikativen Faktoren korrespondierender low- und high-Kanten müssen zueinander relativ prim sein. Zudem müssen die *BMDs reduziert sein. Hier gelten ähnliche Reduktionsregeln wie bei den reduzierten geordneten binären Entscheidungsgraphen. Zeigt die high-Kante eines Knotens v auf das 0-Blatt, so kann der Knoten v gelöscht werden. Alle in v einlaufenden Kanten laufen nun in den Nachfolgerknoten von v ein. Sind die low-Nachfolgerknoten ebenso wie die high-Nachfolgerknoten von zwei Knoten v und w identisch, so kann einer der beiden Knoten v oder w gelöscht werden, wobei die in ihn hineingehenden Kanten auf den anderen Knoten umgelenkt werden.