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
(3)
Boolean Function
Efficient Algorithm
Ordered Binary Decision Diagram
Subscribe
Academic
Publications
Global rebuilding of OBDD's avoiding memory requirement maxima
Global rebuilding of OBDD's avoiding memory requirement maxima,10.1109/43.486279,IEEE Transactions on Computeraided Design of Integrated Circuits and
Edit
Global rebuilding of OBDD's avoiding memory requirement maxima
(
Citations: 3
)
BibTex

RIS

RefWorks
Download
Jochen Bern
,
Christoph Meinel
,
Anna Slobodovii
It is wellknown that the size of an
ordered binary decision diagram
(OBDD) may depend crucially on the order in which the variables occur. In the paper, we describe an implementation of an outputefficient algorithm that transforms an OBDD P representing a
Boolean function
f with respect to one variable ordering π into an OBDD Q that represents f with respect to another variable ordering σ. The algorithm runs in average time O(PQ) and requires O(P+Q) space. The importance of the algorithm is demonstrated by means of experimental results on basically two different applications. In one of them, the algorithm is used merely once. Such transformations are needed to test equivalence or to perform synthesis on OBDD's in which variables appear in different orders. The other application shows a way how to decrease the size of intermediate OBDD representations of a given circuit in the course of its symbolic simulation. Here, the algorithm is used dynamically, whenever the size of the manipulated OBDD's becomes too large
Journal:
IEEE Transactions on Computeraided Design of Integrated Circuits and Systems
, vol. 15, no. 1, pp. 131134, 1996
DOI:
10.1109/43.486279
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.
(
ieeexplore.ieee.org
)
(
www.informatik.unitrier.de
)
(
doi.ieeecomputersociety.org
)
(
ieeexplore.ieee.org
)
More »
Citation Context
(2)
...An outputefficient algorithm was proposed to realize a reordering transformation (
Bern et al., 1996
)...
Wilsin Gosti
,
et al.
FSM Encoding for BDD Representations
...(See [
1
] and [9] for more motivation.) Savick:~ and Wegener showed in [9] that this problem can be deterministically solved in worst case time O (SIZE (B1)" SIZE (B2)" log (SIZE (B2)))...
...The following Mgorithm constructs the desired ~r  @OBDD topdown in a similar way as in [
1
] and [9]...
Jan Behrens
,
et al.
Equivalence Test and Ordering Transformation for ParityOBDDs of Diffe...
References
(17)
GraphBased Algorithms for Boolean Function Manipulation
(
Citations: 5307
)
Randal E. Bryant
Journal:
IEEE Transactions on Computers  TC
, vol. C35, no. 8, pp. 677691, 1986
Finding the Optimal Variable Ordering for Binary Decision Diagrams
(
Citations: 142
)
Steven J. Friedman
,
Kenneth J. Supowit
Journal:
IEEE Transactions on Computers  TC
, vol. 39, no. 5, pp. 710713, 1990
Global rebuilding of OBDD's avoiding memory requirement maxima
(
Citations: 3
)
Jochen Bern
,
Christoph Meinel
,
Anna Slobodovii
Journal:
IEEE Transactions on Computeraided Design of Integrated Circuits and Systems
, vol. 15, no. 1, pp. 131134, 1996
On the Complexity of Constructing Optimal Ordered Binary Decision Diagrams
(
Citations: 16
)
Christoph Meinel
,
Anna Slobodová
Conference:
Mathematical Foundations of Computer Science  MFCS
, pp. 515524, 1994
A Reordering Operation for an Ordered Binary Decision Diagram and an Extended Framework for Combinatorics of Graphs
(
Citations: 9
)
Seiichiro Tani
,
Hiroshi Imai
Conference:
International Symposium on Algorithms and Computation  ISAAC
, pp. 575583, 1994
Sort by:
Citations
(3)
FSM Encoding for BDD Representations
(
Citations: 2
)
Wilsin Gosti
,
Tiziano Villa
,
Alexander Saldanha
,
Alberto L. Sangiovannivincentelli
Journal:
Applied Mathematics and Computer Science
, vol. 17, no. 1, pp. 113124, 2007
Equivalence Test and Ordering Transformation for ParityOBDDs of Different Variable Ordering
Jan Behrens
,
Stephan Waack
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 227237, 1998
Global rebuilding of OBDD's avoiding memory requirement maxima
(
Citations: 3
)
Jochen Bern
,
Christoph Meinel
,
Anna Slobodovii
Journal:
IEEE Transactions on Computeraided Design of Integrated Circuits and Systems
, vol. 15, no. 1, pp. 131134, 1996