Academic
Publications
Graph-Based Algorithms for Boolean Function Manipulation

Graph-Based Algorithms for Boolean Function Manipulation,10.1109/TC.1986.1676819,IEEE Transactions on Computers,Randal E. Bryant

Graph-Based Algorithms for Boolean Function Manipulation   (Citations: 5307)
BibTex | RIS | RefWorks Download
In this paper the authors present a new data structure for representing Boolean functions and an associated set of manipulation algorithms. 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. The 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. The authors present experimental results from applying these algorithms to problems in logic design verification that demonstrate the practicality of the approach.
Journal: IEEE Transactions on Computers - TC , vol. C-35, no. 8, pp. 677-691, 1986
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...To confront this problem Ma and Wonham (Ma and Wonham 2005a, b, 2006) proposed state tree structures (STS), an adaptation of state charts (Harel 1987) which seeks to introduce control hierarchy in a natural way, and exploits the power of binary decision diagrams (BDDs) (Akers 1978; Bryant 1986) for functional representation...

    Wujie Chaoet al. Modular supervisory control and coordination of state tree structures

    • ...Those nullness constraints of our analysis take the form of Boolean formulas, which opens the way to a fast implementation based on binary decision diagrams [5]...
    • ...formulas, efficiently implemented with binary-decision diagrams [5]; – We identify non-null fields with an iterated oracle version of the analysis above; – We couple our first analysis with another static analysis, modelling those fields that are not always non-null, but rather non-null in the context where they are used, because they are protected by a preliminary nullness check; – We show experimentally that the implementation of both ...
    • ...4 and 5, we have coded Boolean formulas as binary decision diagrams [5 ]w ith the BuDDy library (http://sourceforge.net/projects/buddy)...

    Fausto Spoto. Precise null-pointer analysis

    • ...The recent advances on using superior data structure such as a binary decision diagram (BDD) [14], together with a properly formulated implicit enumeration process, have greatly increased the efficiency of enumeration, making the exact symbolic analysis of much larger analog circuits possible...

    Hui Xuet al. Hierarchical exact symbolic analysis of large analog integrated circui...

    • ...If the operator is implemented based on dynamic programming, the time complexity of the algorithm will be [22], where and are the sizes of the BDDs referring to the...

    Sajed Miremadiet al. Symbolic Computation of Reduced Guards in Supervisory Control

    • ...It is assumed that the reader is familiar with the theory, terminology, and implementation of reduced ordered binary decision diagrams [22]‐[24]...

    Tejaswi Gowdaet al. Identification of Threshold Functions and Synthesis of Threshold Netwo...

Sort by: