zbMATH — the first resource for mathematics

Graph-based algorithms for Boolean function manipulation. (English) Zbl 0593.94022
Summary: In this paper we present a new data structure for representing Boolean functions and an associated set of manipulation algorithms. Functions are represented by directed, acyclic graphs in a manner similar to the representations introduced by C. Y. Lee [Bell. Syst. Tech. J. 38, 985-999 (1959)] and S. B. Akers [IEEE Trans. Comput. C-27, 509-516 (1978; Zbl 0377.94038)], but with further restrictions on the ordering of decision variables in the graph. Although a function requires, in the worst case, a graph of size exponential in the number of arguments, many of the functions encountered in typical applications have a more reasonable representation. Our algorithms have time complexity proportional to the sizes of the graphs being operated on, and hence are quite efficient as long as the graphs do not grow too large. We present experimental results from applying these algorithms to problems in logic design verification that demonstrate the practicality of our approach.
Reviewer: Reviewer (Berlin)

94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
94C15 Applications of graph theory to circuits and networks
68W30 Symbolic computation and algebraic computation
68Q25 Analysis of algorithms and problem complexity
Full Text: DOI