next up previous index
Next: The Cache Up: Programmer's Manual Previous: Reference Counts

Complement Arcs


If ADDs are restricted to use only the constants 0 and 1, they behave like BDDs without complement arcs. It is normally easier to write code that manipulates 0-1 ADDs, than to write code for BDDs. However, complementation is trivial with complement arcs, and is not trivial without. As a consequence, with complement arcs it is possible to check for more terminal cases and it is possible to apply De Morgan's laws to reduce problems that are essentially identical to a standard form. This in turn increases the utilization of the cache .

The complement attribute is stored in the least significant bit of the ``else" pointer of each node. An external pointer to a function can also be complemented. The ``then" pointer to a node, on the other hand, is always regular . It is a mistake to use aarc!complement pointer as it is to address memory. Instead, it is always necessary to obtain a regular version of it. This is normally done by calling Cudd_Regular . It is also a mistake to call cuddUniqueInter  with a complemented ``then" child as argument. The calling procedure must apply De Morgan's laws by complementing both pointers passed to cuddUniqueInter  and then taking the complement of the result.

Fabio Somenzi
Tue May 12 18:47:58 MDT 1998