BDD to ZDD conversion

Question

I have a doubt regarding the conversion of BDD to ZDD. We have an algorithm , but it's pretty lengthy. Do we have some other methods to convert BDD to ZDD.

What I am thinking of,

1) BDD to FDD by, Full DNF-> RMNF ( using xor reductions for negations as well) It will give me the FDD equation.

2) Taking this FDD as my next input then, add missing terms as ( missing_term xor 1), then do reduction. It should give my ZDD.

Is it correct ?

Answer 1

What you essentially suggest is to convert the BDD to a FDD and then to a ZDD. I doubt that this is simpler in general.

However, why not undoing the BDD elimination rule to get a non-reduced BDD and then applying the elimination rule of ZDDs? That can also be done on subtrees first to keep the complexity under control.

Comments

Yeah..got it . Can we use any methods for conversion or should we always us algorithms given in the notes?

---

If you have another correct algorithm, it is fine, but then you should explain what you are computing, since otherwise, the people correcting it will be surprised and not convinced at first.

---

Thanks for the clarification.