Reduced Binary Circuits
Reduced Binary Circuit stellen eine Möglichkeit dar, digitale Schaltkreise mit wenig overhead kompakt zu repräsentieren. Resultat ist ein gerichteter azyklischer Graph G bestehend aus Knoten und Kanten.
Interne Knoten repräsentieren einen binären Operator aus der Menge { } und besitzen jeweils 2 Kinder. Blätter hingegen werden mit konstanten Wahrheitswerten {TRUE,FALSE} beschrieben, oder durch eine Variable v VAR, wobei VAR eine beliebige Menge boolscher Variablen darstellt.
Kanten enthalten ein sign-Attibut, das Negierung des Targets, des Zielknotens abgibt.
Kompression wird dabei erreicht, indem zum Einen isomorphe (identische) Teilstrukturen mittels HASHING erfasst und nur einmal explizit in der Datenstruktur repräsentiert werden, zum Andern werden konstante Werte, erfasst und "gekürzt", beispielsweise wird (b TRUE) dargestellt als b.
