Algorithm to compute join in zero suppressed binary decision diagram

Question

What is the algorithm to compute the join of two zero suppressed binary decision diagrams?

I've searched for it for hours now, I just can't find it. It's not in Knuth's book either, as far as I can find, though it does give a definition of the result.

I would prefer not to have to wade through any specific implementation; I find the implementation details very distracting.

The join of ZDDs f and g is { a ∪ b | a ∈ f and b ∈ g }

Forgive me, but what exactly do you mean by "join" here? Union? Intersection? Something else? — hmakholm left over Monica, Aug 30 '11 at 11:21
@Henning Makholm: Neither, it's the set of all unions of all combinations of sets `a` and `b` where `a` is from one ZDD and `b` is from the other. — harold, Aug 30 '11 at 11:32
Okay, that's beyond me. Back when I learned about BDD's each one encoded a single set (of bitstrings), rather than at set of sets. It may have been a simplified version. — hmakholm left over Monica, Aug 30 '11 at 12:17

score 5 · Accepted Answer · answered Aug 30 '11 at 19:37

In my copy of The Art of Computer Programming, Volume 4A this exact question is posed as Exercise 205 in section 7.1.4. It's related to the two previous questions, but the answers to all three are in the back of the book. You might want to check that out as a resource.

I was at a talk Knuth gave a few years ago where he was discussing ZDDs and their algorithms, including how to do join. If you're interested, I believe that the lecture was recorded and should be online here.

Hope this helps!

Thanks, I forgot to look in that part of the book – harold Aug 30 '11 at 21:32 — harold, Aug 30 '11 at 21:32

Algorithm to compute join in zero suppressed binary decision diagram

1 Answers1