Talk:Binary decision diagram

"The resulting BDD is shown in the right figure." -- eh? What right figure? —Preceding unsigned comment added by 200.188.209.86 (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)

Implementation

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)

Looking at other articles on data structures, e.g. Red–black_tree, Disjoint-set_data_structure, and Zero-suppressed_decision_diagram, they do include some (pseudo) code to convey information. Here, the Logical operations on BDDs section could make good use of being expanded in a similar way (for example, showing the SatCount, Restrict, and Apply algorithms for the basics; maybe then also quantification for a more complex operations).

Certainly, the code that was removed back in 2009 may not have been the best way of doing so. But, I'd say that pseudo code would be beneficial to address a weakness of this article. Soelvsten (talk) 07:26, 3 May 2024 (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;
       else
          return old_or_new(φ, hi, lo);
    }
 }

---

Ext links

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)

Lead

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

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:

• Added archive https://web.archive.org/web/20111101143950/http://myvideos.stanford.edu/player/slplayer.aspx?coll=ea60314a-53b3-4be2-8552-dcf190ca0c0b&co=18bcd3a8-965a-4a63-a516-a1ad74af1119&o=true to http://myvideos.stanford.edu/player/slplayer.aspx?coll=ea60314a-53b3-4be2-8552-dcf190ca0c0b&co=18bcd3a8-965a-4a63-a516-a1ad74af1119&o=true

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

This message was posted before February 2018. After February 2018, "External links modified" talk page sections are no longer generated or monitored by InternetArchiveBot. No special action is required regarding these talk page notices, other than regular verification using the archive tool instructions below. Editors have permission to delete these "External links modified" talk page sections if they want to de-clutter talk pages, but see the RfC before doing mass systematic removals. This message is updated dynamically through the template {{source check}} (last update: 5 June 2024).

• 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.

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

What are the operations existential abstraction and universal abstraction?

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

Anyone, please? 185.24.86.101 (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".{{cite web}}: CS1 maint: multiple names: authors list (link) 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)

Problem with Variable ordering section diagram

In the section "Variable ordering", the shown diagrams do not correctly calculate the stated function $f(x_{1},\ldots ,x_{8})=x_{1}x_{2}+x_{3}x_{4}+x_{5}x_{6}+x_{7}x_{8}$. For example, $f(1,1,1,1,0,0,0,0)=0$, yet the diagrams both show $f(1,1,1,1,0,0,0,0)=1$. The file pages for the diagrams contain helpful explanations for how the diagrams were generated, with RML/CrocoPath/GraphViz, and it appears that the function was incorrectly defined there as:

F(x1,x2,x3,x4,x5,x6,x7,x8) :=  (x1="1" & x2="1") 
                             | (x3="1" & x4="1")
                             | (x5="1" & x6="1")
                             | (x7="1" & x8="1");

The binary addition operators in the sum have been translated to boolean OR operators, which is incorrect; binary addition is equivalent to boolean XOR.

User4096 (talk) 00:03, 31 January 2019 (UTC)

I see the source of my confusion. In Boolean logic theory it is common to use the + operator to stand for Boolean OR, not addition modulo 2. User4096 (talk) 22:31, 31 January 2019 (UTC)

Sentential Decision Diagrams

Seems there's an "improvement" on BDDs called SDDs, but wiki has no mention of these. FYI

https://html.duckduckgo.com/html?q=Sentential%20Decision%20Diagrams

79.79.253.53 (talk) 19:31, 14 June 2022 (UTC)

complemented edges diagram

The -11, -3, -5 on the nodes make no sense. Feydun (talk) 22:16, 1 November 2023 (UTC)

Indeed, it seems this picture is a DOT file from the python dd package which also includes debug information. In particular, these values are their indices in the unique node table (fun fact). I have created a replacement by hand that also better aligns with the other figures. Soelvsten (talk) 09:10, 19 March 2024 (UTC)