Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(7)
Binary Decision Diagram
Boolean Function
Data Structure
Functional Requirement
Indexing Terms
Logic Design
Time Complexity
Related Publications
(472)
Symbolic Model Checking: 10
Symbolic Boolean manipulation with ordered binarydecision diagrams
Efficient Implementation of a BDD Package
Binary Decision Diagrams
Chaff: Engineering an efficient SAT solver
Subscribe
Academic
Publications
GraphBased Algorithms for Boolean Function Manipulation
GraphBased Algorithms for Boolean Function Manipulation,10.1109/TC.1986.1676819,IEEE Transactions on Computers,Randal E. Bryant
Edit
GraphBased Algorithms for Boolean Function Manipulation
(
Citations: 5307
)
BibTex

RIS

RefWorks
Download
Randal E. Bryant
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. C35, no. 8, pp. 677691, 1986
DOI:
10.1109/TC.1986.1676819
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.
(
people.inf.ethz.ch
)
(
www.osti.gov
)
(
ieeexplore.ieee.org
)
(
budi.paume.itb.ac.id
)
More »
Citation Context
(3021)
...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 Chao
,
et 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 binarydecision diagrams [
5
]; – We identify nonnull 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 nonnull, but rather nonnull 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 nullpointer 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 Xu
,
et 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 Miremadi
,
et 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 Gowda
,
et al.
Identification of Threshold Functions and Synthesis of Threshold Netwo...
References
(22)
Representation of switching circuits by binary decision programs
(
Citations: 248
)
C. R. Lee
Introduction to switching theory and logical design
(
Citations: 81
)
F. J. Hill
,
G. R. Peterson
Published in 1981.
Decision Trees and Diagrams
(
Citations: 150
)
Bernard M. E. Moret
Journal:
ACM Computing Surveys  CSUR
, vol. 14, no. 4, pp. 593623, 1982
Information transfer and areatime tradeoffs for VLSI multiplication
(
Citations: 25
)
Harold Abelson
,
Peter Andreae
Journal:
Communications of The ACM  CACM
, vol. 23, no. 1, pp. 2023, 1980
Functional testing with binary decision diagrams
(
Citations: 87
)
S. B. Akers
Conference:
Symposium on FaultTolerant Computing  FTCS
, 1978
Sort by:
Citations
(5307)
Modular supervisory control and coordination of state tree structures
Wujie Chao
,
Yongmei Gan
,
Zhaoan Wang
,
W. M. Wonham
Journal:
International Journal of Control  INT J CONTR
, vol. aheadofp, no. aheadofp, pp. 113, 2012
Precise nullpointer analysis
(
Citations: 4
)
Fausto Spoto
Journal:
Software and System Modeling  SOSYM
, vol. 10, no. 2, pp. 219252, 2011
Hierarchical exact symbolic analysis of large analog integrated circuits by symbolic stamps
(
Citations: 2
)
Hui Xu
,
Guoyong Shi
,
Xiaopeng Li
Conference:
Asia and South Pacific Design Automation Conference  ASPDAC
, pp. 1924, 2011
Symbolic Computation of Reduced Guards in Supervisory Control
(
Citations: 2
)
Sajed Miremadi
,
Knut Akesson
,
Bengt Lennartson
Journal:
IEEE Transactions Automation Science and Engineering
, vol. 8, no. 4, pp. 754765, 2011
The Mechanical Verification of a DPLLBased Satisfiability Solver
(
Citations: 2
)
Natarajan Shankar
,
Marc Vaucher
Journal:
Electronic Notes in Theoretical Computer Science  ENTCS
, vol. 269, pp. 317, 2011