(Kronecker) Functional Decision Diagrams

[SSoelvsten]

All other decision diagrams up to this point have had their nodes represent an if-then-else on the variable. In a Functional Decision Diagram (FDD) the semantics of a node is instead and-xor which matches the following positive Davio / Reed–Muller expansion. [Minato01]

f = f[x := 0] + x * (f[x := 0] + f[x := 1])

That is, f.low reflects f[x = 0] (as usual) whereas f.high semantically should be understood as f[x = 0] + f[x = 1]. Minato notes in [Minato01] that the ZDD node-deletion rule might be better than the BDD-one for FDDs.

The interesting thing about FDDs is that some class of functions where BDDs are exponential in size, FDDs are still linear [Drechlser94].

Kronecker Functional Decision Diagrams

The opposite is also true: some cases of linear-sized BDDs have exponential sized FDDs. Hence, with Kronecker Functional Decision Diagrams (KFDD) Drechsler and others [Drechlser94] propose to associate every variable, i.e. every level, with the type of semantics to use. In some ways, this is a level-by-level way of solving the same problem as #440 .

References

• [Drechsler94] Rolf Drechsler et al. “Efficient Representation and Manipulation of Switching Functions Based on Ordered Kronecker Functional Decision Diagrams”. In: 31ST ACM/IEEE Design Automation Conferenc. (1994)

• [Minato01] S. Minato. “Zero-suppressed BDDs and their applications”. In: International Journal on Software Tools for Technology Transfer, 3 (2001)