Dynamic minimization of word-level decision diagrams

Word-Level Decision Diagrams (WLDDs), like *BMDs and K*BMDs, have recently been introduced as a data structure for verification. The size of WLDDs largely depends on the chosen variable ordering, i.e. the ordering in which variables are encountered, and on the decompositions carried out in each node. In this paper we present a framework for dynamic minimization of WLDDs. We discuss the difficulties with previous techniques if applied to WLDDs and present a new approach that efficiently adapts both variable ordering and decomposition type choice. Experimental results demonstrate that this method outperforms “classical” reordering with respect to runtime and representation size during dynamic minimization of word-level functions