Compact OBDDs for 2D-Reducible Functions

The “regularity” of a Boolean function can be exploited for decreasing the cost of its representation or its minimization time. In this paper we study a class of regular Boolean functions called 2D-reducible. We prove that 2D-reducible functions are partially symmetric and we exploit this property to propose a variable ordering for their OBDD representations. The detection of such variable ordering is very efficient since it is polynomial in the SOP representation of the Boolean function.





Anna Bernasconi
Valentina Ciriani
Lorenzo Lago

Pubblicato in

10th International Workshop on Boolean Problems (IWSBP)