Sept. 19, 2002

Workshop on
Boolean Problems

Computing *R**NS* – input determinization

•At each ND node introduce one MV parameter *p**i* with the same range as the node
output.

•Relation at node *i* is replaced
by

–* **p**i* controls the output value of node
*i
*

–the operator* **m* is a special BDD projection operator, defined by Bill Lin, that projects onto the
smallest allowed output value.

•*R**NS *can
be obtained by eliminating all internal nodes and existentially quantifying all parameters.