Talk:Binary decision diagram

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Computer science (Rated C-class, Mid-importance)
WikiProject icon This article is within the scope of WikiProject Computer science, a collaborative effort to improve the coverage of Computer science related articles on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 Mid  This article has been rated as Mid-importance on the project's importance scale.

"The resulting BDD is shown in the right figure." -- eh? What right figure? —Preceding unsigned comment added by (talk) 03:44, 30 April 2008 (UTC)

the sentence "For a long time, this representation was called Alternative Graphs, until it was once renamed." needs fixing... either until it was renamed or until it was once again renamed ???

Two years before Lee the same idea was introduced in former Soviet Union, in Tallinn University of 
Technology  (Ubar 1976). For a long time, this representation was called Alternative Graphs, 
until it was once renamed.

I removed the above from the article, because (Ubar 1976) is not two years before (Lee 1959). Or does it mean before Akers??? I also don't understand the renaming thing. --Dirk 12:34, 1 September 2005 (UTC)

It means before Akers - Ubar from my understanding was the first to impose the sorted restriction on the tree (according to section 3.1 of Jaan Raik's masters thesis also from the same source it doesnt seem like the names are conflicting since there are diffrences in the graphs and the ROBDD can apparently be considered a specialization of the Alternative Graph (havent seen Ubars paper but Raik has co-authered papers with Ubar since then so it would seem he got his information directly from the source) Doctus (20 minutes before I learnt to insert four instead of 3 tilders)

After some more searching it turns out that Alternative Graphs eventually became known as Structurally synthesized binary decision diagrams and the reason nobody new about Ubars work was because it was published in Rusion. Doctus 03:04, 17 April 2006 (UTC)


I have moved the section "Implementation" here (see below). Wikipedia is not a dumping ground for code, and not an implementation howto (see WP:NOTHOWTO for the official policy. Perhaps it is useful for one of the sister projects, such as wikisource. If someone disagrees and intends to put the implementation back into the article, please provide an argument before doing so. Hermel (talk) 19:18, 16 June 2009 (UTC)

This is a crude way to build a BDD in a C like language. Declare the data structure as follows and then proceed accordingly.

 /* The basic data structure */	
 struct vertex
    char *φ;
    struct vertex *hi, *lo;
 /* The interface to the Unique Table */
 struct vertex *old_or_new(char *φ, struct vertex *hi, *lo)
    if(a vertex  v = (φ, hi, lo) exists)
        return  v;
    else {
        v <- new vertex pointing at (φ, hi, lo);
        return  v;

Data Structure for Building the ROBDD

 struct vertex *robdd_build(struct expr <math>f</math>, int i)
    struct vertex *hi, *lo;
    struct char *φ;
    if(equal(f, '0'))
       return v0;
    else if (equal(f, '1'))
       return v1;
    else {
       φ  п(i);
       hi  robdd_build( <math>f (xi = 1)</math>, i+1);
       lo  robdd_build( <math>f (xi = 0)</math>, i+1);
       if(lo == hi) 
          return lo;
          return old_or_new(φ, hi, lo);

Ext links[edit]

Should all of those links be removed? Seems like it goes against WP:NOTLINK. LogicalFinance33 (talk) 22:55, 31 January 2012 (UTC)

The policy states that at Wikipedia we don't allow collection of links as that may dwarf the page but this could be one of those borderline cases where the number of links might be high but each of them quite important from the article's perspective. Any ideas?--Wikishagnik (talk) 18:19, 28 March 2012 (UTC)
I removed the 404 and ones requesting contact by email to get program, others had like 32 downloads or were not even full releases. I kept the best looking ones and removed the tag. Its not really a problem I think. They are different and don't dwarf the article. ChrisGualtieri (talk) 05:50, 16 May 2012 (UTC)
Some (like CMU, CAL and CUDD) are included for historical reasons but some others are actually used by people. I added back JDD and BuDDy and removed some others I felt could be left out instead. Behandeem (talk) 16:41, 5 February 2013 (UTC)


The lead currently begins:

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.

I don't understand why the lead is mentioning NNF and PDAG here. Yes, they are other representations of Boolean functions, but there are many others. Why mention them at all? And why in the lead? --Macrakis (talk) 22:56, 13 December 2013 (UTC)

External links modified[edit]

Hello fellow Wikipedians,

I have just modified one external link on Binary decision diagram. Please take a moment to review my edit. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit this simple FaQ for additional information. I made the following changes:

When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{Sourcecheck}}).

You may set the |checked=, on this template, to true or failed to let other editors know you reviewed the change. If you find any errors, please use the tools below to fix them or call an editor by setting |needhelp= to your help request.

  • If you have discovered URLs which were erroneously considered dead by the bot, you can report them with this tool.
  • If you found an error with any archives or the URLs themselves, you can fix them with this tool.

If you are unable to use these tools, you may set |needhelp=<your help request> on this template to request help from an experienced user. Please include details about your problem, to help other editors.

Cheers.—InternetArchiveBot (Report bug) 19:32, 2 November 2016 (UTC)

What are the operations existential abstraction and universal abstraction?[edit]

I've never heard of them and I have some decent background in set theory. (talk) 17:19, 3 July 2017 (UTC)

Anyone, please? (talk) 08:18, 14 July 2017 (UTC)
Existential abstraction is mentioned in this 1999 paper by Edmund Clarke et al: Edmund Clarke, Somesh Jha, Yuan Lu and Dong Wang. "Abstract BDDs: A Technique for Using Abstraction in Model Checking".  See 'existential abstraction' being defined in section 2.1. They speak as though they are coining the term.
By coincidence I have been trying to check the basis for the section 'Logical operations on BDDs'. I wanted to find references for including 'existential abstraction' and 'universal abstraction' in the list of operations that can be done by polynomial-time graph manipulation. Looking at ref. 16, the Andersen paper, I don't see proper sourcing for any of the items in this section. So my proposal would be to delete the whole section, 'Logical operations on BDDs'. EdJohnston (talk) 04:38, 15 July 2017 (UTC)