Results 221 to 230 of about 2,176 (251)
Some of the next articles are maybe not open access.
An oscillating algorithm for variable ordering in binary decision diagram
ICECS 2000. 7th IEEE International Conference on Electronics, Circuits and Systems (Cat. No.00EX445), 2002In this paper we present a novel heuristic for improving the variable order computation in the binary decision diagram. The proposed algorithm uses two way swapping and it oscillates forward and backward to minimize the number of cycles needed to get the best order. The validity of the proposed approach has been shown using ISCAS 85 benchmarks.
Mohamed Taher +3 more
openaire +1 more source
On the Width of Ordered Binary Decision Diagrams
2014Ordered binary decision diagrams (OBDDs) are a popular data structure for Boolean functions. One of its complexity measures is the width which has been investigated in several areas in computer science like machine learning, property testing, and the design and analysis of implicit graph algorithms.
openaire +1 more source
Finding the optimal variable ordering for binary decision diagrams
IEEE Transactions on Computers, 1987The ordered binary decision diagram is a canonical representation for Boolean functions, presented by R.E. Bryant (1985) as a compact representation for a broad class of interesting functions derived from circuits. However, the size of the diagram is very sensitive to the choice of ordering on the variables; hence, for some applications, such as ...
Steven J. Friedman, Kenneth J. Supowit
openaire +1 more source
Ordered Binary Decision Diagrams and the Davis-Putnam procedure
2005We compare two prominent decision procedures for propositional logic: Ordered Binary Decision Diagrams (Obdds) and the Davis-Putnam procedure. Experimental results indicate that the Davis-Putnam procedure outperforms Obdds in hard constraint-satisfaction problems, while Obdds are clearly superior for Boolean functional equivalence problems from the ...
Tomás E. Uribe, Mark E. Stickel
openaire +1 more source
On random orderings of variables for parity ordered binary decision diagrams
Random Structures and Algorithms, 2000Summary: Ordered Binary Decision Diagrams (OBDDs) are a model for representing Boolean functions. There is also a more powerful variant called parity OBDDs. The size of the representation of a given function depends in both these models on the chosen ordering of the variables. It is known that there are functions such that almost all orderings of their
openaire +2 more sources
A Novel Ordering Method of Binary Decision Diagram
2007 International Conference on Management Science and Engineering, 2007Binary decision diagram (BDD) is an efficient algorithm applied in many domains. When used in the area of system reliability and safety, the BDD technology can improve both qualitative and quantitative analysis of system failures by solving large fault trees.
null Du Su-guo, Sun Yan
openaire +1 more source
On the complexity of constructing optimal ordered binary decision diagrams
1994In the following we prove the widely assumed conjecture that the construction of an optimal OBDD-representation of a Boolean function f is intractable if f is given in terms of DNFs, CNFs, logical circuits, or Ω-BDDs. The problem remains NP-hard if one wants to construct an optimal OBDD-representation merely in such cases its size is bounded by a given
Christoph Meinel, Anna Slobodová
openaire +1 more source
A new scheme to compute variable orders for binary decision diagrams
Proceedings of 4th Great Lakes Symposium on VLSI, 2002Introduces some new methods for estimating the "importance" of a variable in a Boolean function, and uses them to compute variable orders for OBDD construction. These measures are based on information theoretic criteria, and require the computation of the entropy of a variable in a given function.
Jawahar Jain +4 more
openaire +1 more source
Evolving Binary Decision Diagrams with Emergent Variable Orderings
2006Binary Decision Diagrams (BDDs) have become the data structure of choice for representing discrete functions in some design and verification applications: They are compact and efficient to manipulate with strong theoretical underpinnings. However, and despite many appealing characteristics, BDDs are not a representation commonly considered for ...
openaire +1 more source
An optimization technique for ordered (binary) decision diagrams
CompEuro 1992 Proceedings Computer Systems and Software Engineering, 2003The minimum-cost ordered (binary) decision diagram (OBDD) (also a reduced OBDD or ROBDD) is a canonical representation for a logic function, given an ordering on its variables (R. Bryant, 1986). A new optimization technique is presented for suboptimal synthesis of ODDs of complete as well as partial multiple-output Boolean functions.
openaire +1 more source