Entscheidungsbäume mit Sharing

ausgehend von eben definiertem Baum: konstruiere DAG (gerichteten kreisfreien Graphen):

• Blätter zusammenfassen: nur zwei Blätter 0,1
• alle Knoten mit gleichem (v, l, r) mathend000# zusammenfassen
• alle Knoten mit (v, l, r) mathend000# und l = r mathend000# durch l mathend000# ersetzen

reduziertes geordnetes binäres Entscheidungsdiagramm (ROBDD)

Randal E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Transactions on Computers, C-35(8):677-691, 1986