5 ms·
ZDDs: A data structure for families of sets
- madars 15y agoHas anyone encountered ZDDs (or BDDs for that matter) in the industry? This seems to be a relatively new data structure (Knuth says that "it's one of the only really fundamental data structures that came out in the last 25 years") and I haven't seen it referenced outside the academic research.
- swannodette 15y agoFrom the little I've delved into BDDs, they are incredible data structures. I find Decision Diagrams in general fascinating for macro-enabled languages where they can be compiled into very efficient conditional branching code.
- jethroalias97 15y agoI gather they are used by some forms of program verification software. Beyond that, I dunno.
- jethroalias97 15y agoAlthough these days that industry is moving towards sat solvers.
- jchonphoenix 15y agoI wouldn't consider this "industry," but they're used in some classes at CMU for program verification of student's assignments. The canonical example is 15-213 (Intro Computer Systems). That class was also created by Dr. Randall Bryant, who (I believe) invented BDD's.
- davidtgoldblatt 15y agoI haven't used them personally, but my understanding is that BDD's are increasingly used for formal hardware verification.