Write existential quantification over one variable in C, without CUDD's quantification functions.
Cudd_Cofactor(dd, f, g) returns the cofactor of f with respect to a cube g. With a projection variable x, it is f with x set to 1; with Cudd_Not(x), it is f with x set to 0. Like every new result, a cofactor needs Cudd_Ref before the next call, and a release when you are done with it.
Cudd_Cofactor(dd, f, g)
f
g
x
Cudd_Not(x)
Cudd_Ref
Take k = x0 & (x1 | x2) and quantify x1 existentially.
k = x0 & (x1 | x2)
x1
Cudd_Cofactor(dd, k, x1) is k with x1 = 1: x0. Cudd_Cofactor(dd, k, Cudd_Not(x1)) is k with x1 = 0: x0 & x2.
Cudd_Cofactor(dd, k, x1)
k
x1 = 1
x0
Cudd_Cofactor(dd, k, Cudd_Not(x1))
x1 = 0
x0 & x2
Their or, x0 | x0 & x2, is x0: some value of x1 makes k 1 exactly when x0 is 1.
x0 | x0 & x2
So exists(x1: k) is x0, which does not depend on x1.
exists(x1: k)
Write DdNode *exists_var(DdManager *dd, DdNode *f, DdNode *x): it returns, referenced, the existential quantification of f over the variable x, a projection function from Cudd_bddIthVar. Compute it from the two cofactors of f on x, as Module 3 does by hand.
DdNode *exists_var(DdManager *dd, DdNode *f, DdNode *x)
Cudd_bddIthVar
CUDD's quantification functions are not allowed: Cudd_bddExistAbstract, Cudd_bddExistAbstractLimit, Cudd_bddUnivAbstract, Cudd_bddAndAbstract, Cudd_bddAndAbstractLimit, Cudd_bddClippingAndAbstract and Cudd_bddXorExistAbstract.
Cudd_bddExistAbstract
Cudd_bddExistAbstractLimit
Cudd_bddUnivAbstract
Cudd_bddAndAbstract
Cudd_bddAndAbstractLimit
Cudd_bddClippingAndAbstract
Cudd_bddXorExistAbstract
A C file that includes cudd.h and defines exists_var with this name and these parameters. The caller releases the result. The check compiles your file with a hidden test program against CUDD 3.0.0, runs it with AddressSanitizer and UndefinedBehaviorSanitizer, and says which test failed.
cudd.h
exists_var
exists_var returns exists(x: f), referenced.
No reference leaked: Cudd_CheckZeroRef reports 0.
Without CUDD's quantification functions, listed in the task.
Watch the conditions: they show whether the file defines exists_var and names none of the forbidden functions.
Work one case by hand, as in the example, and trace your code on it: which BDDs does it create, and which does it release?
Count the references your function leaves: exactly one, on the result it returns.
Kata 5.3 of Binary Decision Diagrams with CUDD on formal.org. The site checks the answer when you press Check answer; sign in to keep your progress.