Efficient ordered binary decision diagrams minimization based onheuristics of cover pattern processing

摘要

A metric of dynamic binateness for Boolean functions isnintroduced. Based on it and on an analogy between an ordered binaryndecision diagram (OBDD) of a function and the process of recognizingnstrings of patterns representing the function's cover, a near linear,nefficient ordering heuristic for two-level form specified functions isndeveloped. The algorithm stably achieves on average an improvement ofnover 600% in OBDD size in comparison to results from similar computationncomplexity heuristics. The results are comparable to those obtainednusing lexicographic order but are achieved in less CPU time