Operationen mit ROBDDs

binäre boolesche Operation f:

• auf Blättern 0,1 Wert ausrechnen
• auf Knoten mit gleichen Variablen: gemeins. Fallunterscheidung
• auf Knoten mit versch. Variablen: Fallunterscheidung in kleinerer Variablen

der Trick ist: dynamische Optimierung (d. h. von unten nach oben ausrechnen und Ergebnisse merken).

resultierende Laufzeit für f (s, t) ist O(| s| ^. | t|).