Graph driven BDDs – a new data structure for Boolean functions. (English) Zbl 0873.68036

Summary: (Ordered) binary decision diagrams (OBDDs) are used as a data structure for Boolean functions in the logical synthesis process, for verification and test pattern generation, and as part of CAD tools. For several important functions like arithmetical and logical units with quite different functions, the indirect storage access function or the hidden weighted bit function OBDDs have exponential size for any ordering of the variables. Since an ordering of the variables may be stored as a list, OBDDs may also be called list driven BDDs. Two new generalized models of graph driven BDDs are presented. The above mentioned and many other functions can be represented in small polynomial size in this model and the usual operations on OBDDs can be performed efficiently also for graph driven BDDs.


68P05 Data structures
Full Text: DOI


[1] Aborhey, S., Binary decision tree test functions, IEEE Trans. Comput., 37, 1461-1465 (1988) · Zbl 0657.94024
[2] Akers, S. B., Binary decision diagrams, IEEE Trans. Comput., 27, 509-516 (1978) · Zbl 0377.94038
[3] Ashar, P.; Ghosh, A.; Devadas, S., Boolean satisfiability and equivalence checking using general binary decision diagrams, (Internat. Conf. on Comput. Design (1991)), 259-264
[4] Blum, M.; Chandra, A. K.; Wegman, M. N., Equivalence of the free Boolean graphs can be decided probabilistically in polynomial time, Inform. Process. Lett., 10, 2, 80-82 (1980) · Zbl 0444.68059
[5] Brace, K. S.; Rudell, R. L.; Bryant, R. E., Efficient implementation of a BDD package, (27th ACM/IEEE Design Automation Conf. (1990)), 40-45
[7] Bryant, R. E., Symbolic manipulation of Boolean functions using a graphical representation, (22nd ACM/IEEE Design Automation Conf. (1985)), 688-694
[8] Bryant, R. E., Graph-based algorithms for Boolean function manipulation, IEEE Trans. Comput., 35, 677-691 (1986) · Zbl 0593.94022
[9] Bryant, R. E., On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication, IEEE Trans. Comput., 40, 2, 205-213 (1991) · Zbl 1220.68060
[10] Fortune, S.; Hopcroft, J.; Schmidt, E. M., The complexity of equivalence and containment for free single variable program schemes, (5th ICALP. 5th ICALP, Lecture Notes in Computer Science, Vol. 62 (1978), Springer: Springer Berlin), 227-240
[11] Gergov, J.; Meinel, C., Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs, (10th STACS. 10th STACS, Lecture Notes in Computer Science, Vol. 665 (1993), Springer: Springer Berlin), 576-585 · Zbl 0798.68078
[12] Jeong, S.-W.; Plessier, B.; Hachtel, G.; Somenzi, F., Extended BDD’s: Trading off canonicity for structure in verification algorithms, (Internat. Conf. on Computer-Aided Design (1991)), 464-467
[13] Meinel, C., Polynomial size Ω-branching programs and their computational power, Inform. and Comput., 85, 163-182 (1990) · Zbl 0705.68052
[14] Minato, S.; Ishiura, N.; Yajima, S., Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, (27th ACM/IEEE Design Automation Conf. (1990)), 52-57
[15] Sieling, D.; Wegener, I., Reduction of OBDDs in linear time, Inform. Process. Lett., 48, 139-144 (1993) · Zbl 0787.94027
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.