# Can xor and xnor for quasi-reduced BDDs be implemented just like union? [duplicate]

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.

• 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). – Yuval Filmus Aug 13 '13 at 6:32
• What are "quasi-reduced" BDDs, is that a standard notion? Have you tried the algorithm for some examples? – Raphael Aug 13 '13 at 8:22
• 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.) – Raphael Aug 13 '13 at 8:53
• 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. – compengr Aug 13 '13 at 16:44
• 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. – compengr Aug 13 '13 at 16:45