
inversion algorithm
Hi,
I need to write a pesudocode about InvertRelation function for 2level Binary Decision diagrams.
InvertRelation takes as input a 2Llevel quasireduced BDD rooted at r encoding a relation R : B^{L} → 2^{{BL}} and returns the 2Llevel quasireduced BDD rooted at s encoding the relation R^{{−1}} :B^{L} →2^{{BL}},that is, j ∈ R(i) iff i ∈ R^{{−1}}(j).
the input BDD r uses the variable order x′1, x1, ..., x′L, xL and that the result BDD s uses the variable order x1,x′1,...,xL,x′L. Thus r is at level L and its children are at level L′, while s is at level L′ and its children are at level L.
Any help is appreciated.