Entscheidungsgraphen mit Sharing

DAG (gerichteter kreisfreier Graph) G = (V, E) heißt geordnetes binäres Entscheidungsdiagramm, falls:

heißt geordnet, falls Variablen auf jedem Pfad absteigen

heißt reduziert (ROBDD), falls außerdem

Randal E. Bryant. Graph-Based Algorithms for Boolean Function Manipulation. IEEE Trans.Comp., C-35(8):677-691, 1986 http://www.cs.cmu.edu/~bryant/pubdir/ieeetc86.pdf


2014-07-06