Below is an algorithm for union of two quasi reduced BDDs p and q resulting in r.

bdd Union(bdd p, bdd q) 
  local bdd r;
1 if p=0 or q=1 then return q;
2 if q=0 or p=1 then return p;
3 if p=q then return p;
4 if Cachecontainsentry⟨UnionCODE,{p,q}:r⟩ then return r;
  //p.lvl = q.lvl in case of quasi reduced BDDs
5 r ← UniqueTableInsert(p.lvl, Union(p[0], q[0]), Union(p[1], q[1]));
6 enter⟨UnionCODE,{p,q}:r⟩ in Cache;
7 return r;

Since there is no variable skipping, p.lvl is always equal to q.lvl. I have a question about this algorithm.

If I want to implement Xor or Xnor for quasi-reduced BDDs, can it be done the same way as union or should I implement the expression pq' + p'q where q' = !q.

  • $\begingroup$ Can you write your algorithm in pseudocode? We don't know what the various functions you call do (for example, what order are their parameters). $\endgroup$ – Yuval Filmus Aug 13 '13 at 6:32
  • $\begingroup$ What are "quasi-reduced" BDDs, is that a standard notion? Have you tried the algorithm for some examples? $\endgroup$ – Raphael Aug 13 '13 at 8:22
  • $\begingroup$ How does this differ from your older question, besides being condiderably less meaty? (Moderator's note: please register an account so you can take proper ownership of your posts; you will be able to edit, then.) $\endgroup$ – Raphael Aug 13 '13 at 8:53
  • $\begingroup$ It differs from my older question that was conversion of algorithm from fully-reduced to quasi reduced. I was asked by a moderator to create a separate post for this algorithm. I am a registered user to answer your second question. $\endgroup$ – compengr Aug 13 '13 at 16:44
  • $\begingroup$ Quasi-reduced BDDs are produced when we merge the nodes of OBDD such that every non-terminal node has children. In case of Fully-reduced, the redundant nodes of OBDD are merged as well as deleted. $\endgroup$ – compengr Aug 13 '13 at 16:45