Binary moment diagram とは

バイナリモーメントダイアグラム(BMD)は、ブール値(BDDなど)のようなドメイン上の線形関数へのバイナリ決定図(BDD)の一般化であるが、整数または実数への一般化でもある。
彼らはBDDに匹敵する複雑さを持つブール関数を扱うことができますが、BDDで非常に非効率的に扱われるいくつかの関数は、BMD、とりわけ乗算によって容易に処理されます。
BMDの最も重要な特性は、BDDの場合と同様に、各関数は厳密に1つの正準表現を持ち、これらの表現に対して多くの演算を効率的に実行できることです。
BDDとBMDを区別する主な機能は、ポイントワイズダイアグラムの代わりにリニアを使用し、エッジを重み付けして使用します。
表現の標準を保証する規則は次のとおりです。
 順序の高い変数に対する決定は、順序の低い変数に対する決定を指し示すだけかもしれない。 2つのノードは同一ではない(正規化において、これらのノードの1つに対するすべての参照を別のノードへの参照と置き換える必要がある)。ノードは0に等しいすべての決定部分を有することはできない(そのようなノードへのリンクは、 )エッジにはウェイトゼロがありません(このようなエッジはすべて0に直接リンクする必要があります)。エッジの重みは共起する必要があります。このルールやそれに相当するものがなければ、関数は多くの表現を持つことができます。たとえば、2x + 2は2・(1 + x)または1・(2 + 2x)で表すことができます。