Stack Overflow
Stack Overflow

Questions tagged [binary-decision-diagram]

In the field of computer science, a binary decision diagram (BDD) or branching program, like a negation normal form (NNF) or a propositional directed acyclic graph (PDAG), is a data structure that is used to represent a Boolean function. On a more abstract level, BDDs can be considered as a compressed representation of sets or relations.

Wikipedia Article: http://en.wikipedia.org/wiki/Binary_decision_diagram

Introduction to Binary Decision Diagrams, Henrik Reif Andersen [PDF]: http://www.cs.unb.ca/~gdueck/courses/cs4835/bdd97.pdf

Fun With Binary Decision Diagrams, Donald Knuth [Video]: http://myvideos.stanford.edu/player/slplayer.aspx?coll=ea60314a-53b3-4be2-8552-dcf190ca0c0b&co=18bcd3a8-965a-4a63-a516-a1ad74af1119&o=true

87 questions
10
votes
1 answer

Heuristics for estimating the efficiency of Reduced Ordered Binary Decision Diagrams?

Reduced Ordered Binary Decision Diagrams (ROBDD) are an efficient data structure for boolean functions of multiple variables f(x1,x2,...,xn). I would like to get an intuition for how efficient they are. For instance, for data compression, we know…
Heinrich Apfelmus
  • 11,034
  • 1
  • 39
  • 67
8
votes
0 answers

Proposing an algorithm for arbitrary shape Bit Matrix Transposition with BDD-like structure

We consider a bit matrix (n x m) to be a regular array containing n lines of integers of size m. I have looked in Hacker's Delight and in other sources and the algorithms I found for this were rather specialized: square matrices with powers of two…
ZakC
  • 479
  • 3
  • 11
6
votes
3 answers

How to efficiently implement binary decision diagrams (BDD)?

Background about binary decision diagrams can be found here BDD on wikipedia. The simplest approach is to build BDT (Binary Decision Tree) and then reduce it due to two rules: - Merge any isomorphic subgraphs. - Eliminate any node whose two children…
Tomek Tarczynski
  • 2,785
  • 8
  • 37
  • 43
6
votes
1 answer

Intersection of Zero-Suppressed BDD -- Implementing polynomials using ZDDs

I'm trying to implement univariate polynomials using ZDDs, as suggested in a comment in an other question. I've read the paper of S. Minato(you may download it here), but I don't understand how to implement the operations on these ZDDs. The idea in…
Bakuriu
  • 98,325
  • 22
  • 197
  • 231
5
votes
1 answer

Algorithm to compute join in zero suppressed binary decision diagram

What is the algorithm to compute the join of two zero suppressed binary decision diagrams? I've searched for it for hours now, I just can't find it. It's not in Knuth's book either, as far as I can find, though it does give a definition of the…
harold
  • 61,398
  • 6
  • 86
  • 164
5
votes
3 answers

Extended find of unique tuples in a relation represented by a BDD

Consider {<1,2>, <1,3>, <1,7>, <0,4>} as the set of tuples of a relation R. Now consider that R is represented (via its membership function) by a BDD. That is, The BDD representing R depends on variables {x1,x2, y1, y2, y3} where {x1, x2} are used…
user1975278
  • 83
  • 5
4
votes
1 answer

Does anyone know of a any C# BDD(Binary Decision Diagram) packages?

How can i implement binary decision diagrams (BDD)? i want to implement the minimization of BDDs based on cultural algorithms and the circuit fault detection by BDDs.
sarah
  • 59
  • 2
4
votes
1 answer

Learning Binary Decision Diagrams (BDDs) from data in Python

Is it possible to learn Binary Decision Diagrams (BDDs) from data (as in a machine learning fashion)? If so, how? Background: I've seen some tools in Python to do this task in e.g., Decision Trees (DTs) with scikit-learn, but I have not seen any for…
lisandrojim
  • 509
  • 5
  • 18
4
votes
2 answers

CUDD: Quantification of ZDDs

I'm working with CUDD (https://github.com/ivmai/cudd) to use bdd and zdd functionality for model checking, and am wondering how i can quantify over zdds. For bdds there are the functions bddExistAbstract and bddUnivAbstract (see…
Daniel Miedema
  • 159
  • 7
4
votes
2 answers

Cudd Package : Binary decison diagrams

Can anyone point some good material on Cudd package. I am looking for some concise matter here. The one at http://vlsi.colorado.edu/~fabio/CUDD/ doesn't seem to give a good introduction to the matter. Any video lectures relating to BDD and its…
rob
  • 121
  • 3
4
votes
1 answer

Generation of Multi-Output BDD

I am using the CUDD package to generate the BDD, corresponding to an input benchmark file, in PLA format. For a benchmark function with 3 input pins (say) and, 5 output pins (say), I am getting 5 output BDDS corresponding to the 5 outputs. But, I…
CA_RS
  • 41
  • 2
4
votes
3 answers

Convert Decision Table To Decision Tree

How to convert or visualize decision table to decision tree graph, is there an algorithm to solve it, or a software to visualize it? For example, I want to visualize my decision table below: https://i.stack.imgur.com/Qe2Pw.jpg
Putra Ardiansyah
  • 5,249
  • 4
  • 25
  • 37
4
votes
2 answers

How to encode integers in BDDs

I'm implementing in Java. At the moment I'm trying to use BDDs (Binary Decision Diagramms) in order to store relations in a datastructure. E.g. R={(3,2),(2,0)} and the corresponding BDD: For this reason I was looking for libraries, which have BDD…
tralala
  • 163
  • 2
  • 16
4
votes
3 answers

Create Reduced Ordered Binary Decision Diagram (ROBDD) from truth table

Is there a software package (preferable an application, not library) that creates Reduced Ordered Binary Decision Diagrams (ROBDDs) from a given truth table (in some text format)?
tomash
  • 687
  • 1
  • 6
  • 17
3
votes
1 answer

Storing BDD in a file using CUDD/DDDMP package?

I have successfully created BDD using CUDD package. I am also able to visualize it using some already built tool. I am interested in storing BDD in a file using DDDMP package of CUDD. I read that Dddmp_cuddBddStore() is doing that for us. I am not…
hemant yadav
  • 31
  • 1
  • 2
1
2 3 4 5 6