Nulový potlačený rozhodovací diagram - Zero-suppressed decision diagram

Tento článek obsahuje a seznam doporučení, související čtení nebo externí odkazy, ale jeho zdroje zůstávají nejasné, protože mu chybí vložené citace. Prosím pomozte zlepšit tento článek představuji přesnější citace. (Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

A nulový potlačený rozhodovací diagram (ZSDD nebo ZDD) je zvláštní druh binární rozhodovací diagram (BDD) s pevným variabilním uspořádáním. Tento datová struktura poskytuje kanonicky kompaktní zobrazení množin, zvláště vhodných pro určité kombinatorické problémy. Připomeňte si strategii redukce OBDD, tj. Uzel je odstraněn z rozhodovacího stromu, pokud oba okraje směřují ke stejnému uzlu. Naproti tomu je uzel v ZDD odstraněn, pokud jeho kladná hrana ukazuje na koncový uzel 0. To poskytuje alternativní silnou normální formu se zlepšenou kompresí řídkých množin. Je založen na pravidle redukce navrženém Shin-ichi Minato v roce 1993.

Pozadí

V Binární rozhodovací diagram, a Booleovská funkce může být reprezentován jako rootovaný, acyklický graf, který se skládá z několika rozhodovacích uzlů a koncových uzlů. V roce 1993 byl upraven Shin-ichi Minato z Japonska Randal Bryant BDD pro řešení kombinatorické problémy. Jeho „nulově potlačené“ BDD mají za cíl reprezentovat a manipulovat řídké sady bitových vektorů. Pokud jsou data problému reprezentována jako bitové vektory délky n, pak libovolná podmnožina vektorů může být reprezentována booleovskou funkcí přes n proměnných, které dávají 1, když je v sadě vektor odpovídající přiřazení proměnné.

Podle Bryanta je možné použít formy logické funkce vyjádřit problémy týkající se součtu produktů. Takové formy jsou často reprezentovány jako sady „kostek“, z nichž každá je označena řetězcem obsahujícím symboly 0, 1 a -. Například funkce ${displaystyle ({ar {x}} _ {1} země x_ {2}) lor ({ar {x}} _ {2} igoplus x_ {3})}$ lze ilustrovat sadou ${displaystyle {01 -, - 11, -00}}$. Použitím bitů 10, 01 a 00 k označení symbolů 1, 0 a - v uvedeném pořadí, lze představovat výše uvedenou sadu s bitovými vektory ve formě ${displaystyle {011000,001010,000101}}$. Všimněte si, že sada bitových vektorů je řídká, protože počet vektorů je menší než 2ⁿ, což je maximální počet bitových vektorů, a sada obsahuje mnoho prvků rovných nule. V tomto případě lze uzel vynechat, pokud nastavení proměnné uzlu na 1 způsobí, že funkce poskytne 0. To je vidět za podmínky, že 1 v nějaké bitové pozici znamená, že vektor není v množině. U řídkých sad je tato podmínka běžná, a proto je možné mnoho eliminací uzlů.

Společnost Minato prokázala, že ZDD jsou zvláště vhodná pro kombinatorické problémy, jako jsou klasické problémy v dvouúrovňová logická minimalizace, rytířské turné, simulace poruch, analýza časování, problém N-královen, stejně jako slabé rozdělení. Použitím ZDD lze zmenšit velikost reprezentace sady n-bitových vektorů v OBDD maximálně o faktor n. V praxi je optimalizace statisticky významný.

Definice

Definujeme Zero-Suppressed Decision Diagram (ZDD) jako jakýkoli směrovaný acyklický graf tak, že:

1. A koncový uzel je buď:

• Speciální uzel ((PRAVÝ uzel) nebo:
• Speciální uzel ((uzel FALSE).

2. Každý neterminální uzel splňuje následující podmínky:

A. Uzel je označen kladným celým číslem v. Tento štítek nemusí být jedinečný.

b. Uzel má výstupní stupeň 2. Jedna z odchozích hran se jmenuje „LO“ a druhá „HI“. (V diagramech lze nakreslit tečkované čáry pro hrany LO a plné čáry pro hrany HI)

C. Cílový uzel je buď terminál, nebo označený celým číslem striktně větším než v. Tudíž lze v diagramech vynechat šipky, protože z popisů lze odvodit směry hran.

d. Hrana HI nikdy neukazuje na uzel ⊥.

3. Existuje přesně jeden uzel s nulovým stupněm - kořenový uzel. Kořenový uzel je buď terminál, nebo označen nejmenším celým číslem v diagramu.

4. Pokud mají dva uzly stejný štítek, pak jejich hrany LO nebo HI ukazují na různé uzly. Jinými slovy, neexistují žádné redundantní uzly.

Říkáme Z neredukovaný ZDD, pokud hrana HI ukazuje na uzel or nebo podmínka 4 selže.

Obrázek 1 a Obrázek 2: Odstranění uzlu ZDD a sdílení uzlů

V počítačových programech lze logické funkce vyjádřit v bitech, takže the uzel a ⊥ uzel lze reprezentovat 1 a 0. Z výše uvedené definice můžeme účinně reprezentovat sady kombinací použitím dvou pravidel na BDD:

1. Odstraňte všechny uzly, jejichž 1 hrana směřuje k 0-koncovému uzlu. Potom připojte přímo hranu k druhému subgrafu, jak je znázorněno na obrázku 1.

2. Sdílejte všechny ekvivalentní dílčí grafy stejně jako u původních BDD.

Pokud jsou počet a pořadí vstupních proměnných pevné, BDD s potlačením nuly představuje jedinečnou booleovskou funkci (jak je ukázáno na obrázku 2, je možné použít BDD k reprezentaci booleovského binárního stromu).

Představující rodinu sad

Nechť F je ZDD. Nechť v je jeho kořenový uzel. Pak:

1. Pokud v = ⊥, pak nemohou existovat žádné další uzly a F představuje Ø, prázdnou rodinu.

2. Pokud v = ⊤, pak nemohou existovat žádné další uzly a F představuje rodinu obsahující pouze prázdnou množinu {Ø}. Říkáme tomu jednotková rodina a označujeme to.

3. Pokud má v dvě děti. Nechť v0 je uzel LO a v1 je uzel HI. Nechť Fi je rodina představovaná ZDD zakořeněným na vi, což lze ukázat důkazem indukce. Potom F představuje rodinu

${displaystyle F_ {0} cup {alpha cup {v} mid alpha in F_ {1}}}$

Jeden může představovat větev LO jako množiny v F, které neobsahují proti:${displaystyle F_ {0} = {alpha: alpha in F, votin alpha}}$

A větev HI jako množiny v F, které obsahují proti:${displaystyle F_ {1} = {alpha ackslash {v}: alpha in F, vin alpha}}$

Obrázek 3: Základní rodina v ZDD

Obrázek 4: ${displaystyle {emptyset} cup {emptyset cup {2}} = {emptyset, {2}}}$

Příklad

Obrázek 5: ${displaystyle {{2}} pohár {prázdný pohár {1}} = {{1}, {2}}}$

Obrázek 6:${displaystyle {{1} pohár {2}} = {{1,2}}}$

Obrázek 3: Rodina ${displaystyle emptyset cup {emptyset cup {2}} = {{2}}}$. Můžeme to nazvat ${displaystyle e_ {2}}$, základní rodina. Základní rodiny se skládají z formy ${displaystyle {{n}}}$, a jsou označeny ${displaystyle e_ {n}}$.

Obrázek 4: Rodina ${displaystyle {emptyset} cup {emptyset cup {2}} = {emptyset, {2}}}$

Obrázek 5: Rodina ${displaystyle {{2}} pohár {prázdný pohár {1}} = {{1}, {2}}}$

Obrázek 6: Rodina ${displaystyle {{1} pohár {2}} = {{1,2}}}$

Funkce

Jedním z rysů ZDD je, že forma nezávisí na počtu vstupních proměnných, pokud jsou sady kombinací stejné. Před generováním grafů není nutné opravit počet vstupních proměnných. ZDD automaticky potlačují proměnné pro objekty, které se nikdy neobjeví v kombinaci, a tudíž účinnost pro manipulaci s řídkými kombinacemi. Další výhodou ZDD je, že počet 1 cest v grafu je přesně stejný jako počet prvků v kombinační sadě. V původních BDD tuto vlastnost narušuje eliminace uzlu. ZDD jsou proto lepší než jednoduché BDD, které představují sady kombinací. Při představování běžných booleovských funkcí je však lepší použít původní BDD, jak je znázorněno na obrázku 7.

Obrázek 7: Manipulace s bity a základní operace. Obrázek 8: Potlačení irelevantních proměnných

Základní operace

Zde máme základní operace pro ZDD, protože se mírně liší od operací původních BDD. Jeden může odkazovat na obrázek 8 pro příklady generované z níže uvedené tabulky.

Empty () vrací ø (prázdná množina)

Base () vrací {0}

Subset1 (P, var) returns the subset of P such as var = 1

Subset0 (P, var) vrací podmnožinu P, jako je var = 0

Změna (P, var) vrátí P, když var je obráceně

Union (P, Q) se vrací (${displaystyle Pcup Q}$)

Intsec (P, Q) se vrací (${displaystyle Pcap Q}$)

Diff (P, Q) vrací (${displaystyle P-Q}$)

Počet (P) se vrací ${displaystyle leftvert Pightvert}$. (počet prvků)

V ZDD není žádná operace NOT, což je základní operace v originálních BDD. Důvodem je, že sada doplňků ${displaystyle {ar {P}}}$ nelze vypočítat bez definice univerzální množiny ${displaystyle U}$. V ZDD ${displaystyle {ar {P}}}$ lze vypočítat jako Diff (U, P).

Algoritmy

Předpokládat${displaystyle leftvert Pightvert = leftvert P_ {0} ightvert + leftvert P_ {1} ightvert}$ , můžeme rekurzivně vypočítat počet sad v ZDD, což nám umožní získat 34. sadu 54člennou rodinu. Náhodný přístup je rychlý a na ZDD lze efektivně provádět jakoukoli operaci možnou pro řadu sad.

Podle Minata lze výše uvedené operace pro ZDD provádět rekurzivně jako původní BDD. Abychom jednoduše popsali algoritmy, definujeme postup Getnode (horní, P0, P1) který vrací uzel pro proměnnou horní část a dva podgrafy P0 a P1. Můžeme použít hashovací tabulku nazvanou uniq-table, aby byl každý uzel jedinečný. Odstranění uzlu a sdílení jsou spravovány pouze uživatelem Getnode ().

 Getnode (top, P0, P1) {if (P1 == ø) návrat P0; / * eliminace uzlu * / P = hledat uzel s (top, P0, P1) v uniq-tabulce; pokud (P existuje) vrátit P; / * sdílení uzlu * / P = generovat uzel pomocí (top, P0, P1); připojit P k tabulce uniq; návrat P; }

Použitím Getnode (), můžeme následně představovat další základní operace následovně:

 Subset1 (P, var) {if (P.top  var) return Getnode (P.top, Subset1 (P0, var), Subset1 (P1, var)); } 

 Subset0 (P, var) {if (P.top  var) return Getnode (P.top, Subset0 (P0, var), Subset0 (P1, var)); } 

 Change (P, var) {if (P.top  var) return Getnode (P.top, Change (P0, var), Change (P1, var)); } Union (P, Q) {if (P == ø) return Q; if (Q == ø) návrat P; if (P == Q) návrat P; if (P.top> Q.top) return Getnode (P.top, Union (P0, Q), P1); if (P.top 
 Intsec (P, Q) {if (P == ø) návrat ø; if (Q == ø) návrat ø; if (P == Q) návrat P; if (P.top> Q.top) return Intsec (P0, Q); if (P.top 
 Diff (P, Q) {if (P == ø) return ø; if (Q == ø) návrat P; if (P == Q) návrat ø; if (P.top> Q.top) return Getnode (P.top, Diff (P0, Q), P1;) if (P.top 
 Count (P) {if (P == ø) return 0; if (P == {ø}) vrátit 1; návratový počet (P0) + počet (P1); }
V nejhorším případě tyto algoritmy potřebují exponenciální čas pro počet proměnných; můžeme však zlepšit výkon pomocí mezipaměti, která si podobným způsobem v BDD zapamatuje výsledky nedávných operací. Mezipaměť zabraňuje duplicitním popravám ekvivalentních dílčích grafů. Bez duplikátů mohou algoritmy pracovat v čase, který je úměrný velikosti grafů, jak je znázorněno na obrázku 9 a 10.
  
Obrázek 9: Výsledky v problému N-Queens Obrázek 10: Výkonnost ZDD vs. BDD
aplikace
ZDD jako slovníky
ZDD lze použít k vyjádření pětipísmenných slov angličtiny, množiny WORDS (o velikosti 5757) z Stanford GraphBase Jedním ze způsobů, jak to udělat, je zvážit funkci ${displaystyle f (x_ {1}, ..., x_ {25})}$ to je definováno jako 1 právě tehdy, když je to pět čísel ${displaystyle (x_ {1}, ..., x_ {5}) _ {2}}$, ${displaystyle (x_ {6}, ..., x_ {10}) _ {2}}$, ..., ${displaystyle (x_ {21}, ..., x_ {25}) _ {2}}$ zakódovat písmena anglického slova, kde ${displaystyle a = (00001) _ {2}}$, ..., ${displaystyle z = (11010) _ {2}}$. Například,${displaystyle f (0,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,0, 0, x_ {25}) = x_ {25}}$. Funkce 25 proměnných má Z (f) = 6233 uzlů - což není špatné pro představení 5757 slov. binární stromy, zkouší nebo hash tabulky, ZDD nemusí být nejlepší pro dokončení jednoduchého vyhledávání, přesto je efektivní při načítání dat, která jsou specifikována pouze částečně, nebo dat, u nichž se má pouze přibližně shodovat s klíčem. Složité dotazy lze snadno zpracovat. ZDD navíc nezahrnují tolik proměnných. Ve skutečnosti lze pomocí ZDD představovat těchto pět písmenných slov jako řídkou funkci ${displaystyle F (a_ {1}, ..., z_ {1}, a_ {2}, ..., z_ {2}, ..., a_ {5}, ..., z_ {5}) }$který má 26 × 5 = 130 proměnných, kde proměnná ${displaystyle a_ {2}}$ například určuje, zda je druhé písmeno „a“. Abychom reprezentovali slovo „bláznivý“, můžeme provést F, když ${displaystyle c_ {1} = r_ {2} = a_ {3} = z_ {4} = y_ {5} = 1}$ a všechny ostatní proměnné jsou 0. F tedy lze považovat za rodinu skládající se z 5757 podmnožin ${displaystyle {w_ {1}, h_ {2}, i_ {3}, c_ {4}, h_ {5}}}$atd. S těmito 130 proměnnými je ZDD velikost Z (F) ve skutečnosti 5020 místo 6233. Podle Knutha je ekvivalentní velikost B (F) pomocí BDD 46 189 - výrazně větší než Z (F). Navzdory podobným teoriím a algoritmům ZDD překonávají BDD pro tento problém s poměrně velkou rezervou. ZDD nám proto umožňují provádět určité dotazy, které jsou pro BDD příliš obtížné. Složité rodiny podmnožiny lze snadno sestavit ze základních rodin. Chcete-li hledat slova obsahující určitý vzor, ​​můžete k výpočtu použít rodinnou algebru na ZDD ${displaystyle (F / P) sqcup P}$ kde P je vzor, ​​např ${displaystyle a_ {1} sqcup h_ {3} sqcup e_ {5}}$.
  
Obrázek 11: mřížka tři ku třem
ZDD představují jednoduché cesty
K zastupování lze použít ZDD jednoduché cesty v neorientovaný graf. Například existuje 12 způsobů, jak přejít z levého horního rohu mřížky tři o tři (zobrazené na obrázku 11) do pravého dolního rohu, aniž byste dvakrát navštívili jakýkoli bod.
  
Obrázek 12: 12 možných cest k přechodu jednoho rohu do druhého úhlopříčného rohu
Tyto cesty mohou být reprezentovány ZDD znázorněným na obrázku 13. V tomto ZDD získáme první cestu převzetím větví HI v uzlu 13, uzlu 36, uzlu 68 a uzlu 89 ZDD (větve LO, které jednoduše přejdou na to jsou vynechány). Ačkoli ZDD na obrázku 13 se v žádném případě nemusí zdát významná, výhody ZDD se stanou zřejmými, jak se mřížka zvětšuje. Například pro mřížku osm o osm se počet jednoduchých cest z rohu do rohu ukáže být 789, 360 053 252 (Knuth). Cesty lze ilustrovat pomocí 33580 uzlů pomocí ZDD.
  
Obrázek 13: ZDD pro jednoduché cesty mřížky tři ku třem
Skutečný světový příklad jednoduchých cest navrhl Randal Bryant: „Předpokládám, že bych chtěl podniknout prohlídku kontinentálních USA, navštívit všechny státní úřady a projít každým státem pouze jednou. Jakou trasu bych měl použít, abych minimalizoval celkovou vzdálenost? “ Obrázek 14 ukazuje neorientovaný graf tohoto plánu, čísla označující nejkratší vzdálenosti mezi sousedními hlavními městy. Problém je vybrat podmnožinu těchto hran, které tvoří a Hamiltonova cesta nejmenší celkové délky. Každý Hamiltonova cesta v tomto grafu musí začínat nebo končit v Augustě v Maine (ME). Předpokládejme, že jeden začíná v CA. Lze najít ZDD, který charakterizuje všechny cesty od CA po ME. Podle Knutha se ukázalo, že tento ZDD má pouze 7850 uzlů a efektivně ukazuje, že je možné přesně 437 525 772 584 jednoduchých cest z CA do ME. Podle počtu hran je generující funkce 
                      ${displaystyle 4z ^ {11} + 124z ^ {12} + 1539z ^ {13} + ... + 33385461z ^ {46} + 2707075z ^ {47}}$;
takže nejdelší takové cesty jsou Hamiltonian, s velikostí 2 707 075. ZDD v tomto případě jsou efektivní pro jednoduché cesty a Hamiltonovské cesty.
  
Obrázek 14: Neusměrněný graf států kontinentální USA
problém s osmi královnami
Definujte 64 vstupních proměnných, které představují čtverce na šachovnici. Každá proměnná označuje přítomnost nebo nepřítomnost královny na tomto čtverci. Zvažte to, 
V konkrétním sloupci je pouze jedna proměnná „1“.
V konkrétním řádku je pouze jedna proměnná „1“.
Na konkrétní diagonální linii je jedna nebo žádná proměnná „1“.
Ačkoli lze tento problém vyřešit konstrukcí OBDD, je efektivnější použít ZDD. Konstrukce ZDD pro problém s 8 královnami vyžaduje 8 kroků od S1 po S8. Každý krok lze definovat takto:
S1: Představuje všechny možnosti uvedení královny do první řady.
S2: Představuje všechny možnosti, jak dát královnu do druhé řady, aby neporušila první královnu.
S3: Představuje všechny možnosti uvedení královny do třetí řady tak, aby neporušovala předchozí královny.
…
S8: Představuje všechny možnosti uvedení královny do osmé řady tak, aby neporušovala předchozí královny.
ZDD pro S8 se skládá ze všech potenciálních řešení problému 8-královen. U tohoto konkrétního problému může ukládání do mezipaměti významně zlepšit výkon algoritmu. Použití mezipaměti k zamezení duplikátů může zlepšit problémy s N-Queens až 4,5krát rychleji než použití pouze základních operací (jak je definováno výše), jak je znázorněno na obrázku 10.
Problém s rytířským turné
Problém s rytířským turné má historický význam. Rytířský graf obsahuje n2 vrcholů, které znázorňují čtverce šachovnice. Okraje ilustrují legální pohyby rytíře. Rytíř může navštívit každé pole hrací plochy přesně jednou. Olaf Schröer, M. Löbbing a Ingo Wegener přistoupili k tomuto problému, konkrétně na desce, přiřazením booleovských proměnných pro každou hranu v grafu, celkem 156 proměnných k označení všech hran. Řešení problému lze vyjádřit 156bitovým kombinačním vektorem. Podle Minata je výstavba ZDD pro všechna řešení příliš velká na to, aby byla řešena přímo. Je snazší rozdělit a dobýt. Rozdělením problémů na dvě části desky a konstrukcí ZDD v podprostorech lze vyřešit problém prohlídky The Knight’s s každým řešením obsahujícím 64 hran. Protože však graf není příliš řídký, výhoda použití ZDD není tak zřejmá. 
Simulace poruch
N. Takahashi a kol. Navrhli metodu simulace poruch, která při použití OBDD dává více poruch. Tato deduktivní metoda přenáší chybové sady z primárních vstupů na primární výstupy a zachycuje poruchy na primárních výstupech. Vzhledem k tomu, že tato metoda zahrnuje unate cube set expressions, ZDDs are more efficient. Optimalizace z ZDD ve výpočtech množiny krychle bez vazby naznačují, že ZDD by mohly být užitečné při vývoji CAD systémů VLSI a v mnoha dalších aplikacích.
Viz také
Objednané binární rozhodovací schéma (OBDD)
Diagram rozhodnutí o permutaci (πDD)
Sekvenční rozhodovací diagram (SeqDD)
Diagram sentimentálního rozhodnutí (SDD)
Schéma skupinového rozhodnutí (GDD)
Dostupné balíčky
CUDD: Balíček BDD napsaný v jazyce C, který implementuje BDD a ZBDD, University of Colorado, Boulder
JDD „Knihovna java, která implementuje běžné operace BDD a ZBDD
Graphillion „Implementace softwaru ZDD založená na Pythonu
[1] „Implementace CWEB ZDD Donalda Knutha.
Reference
Shin-ichi Minato, “Nulové potlačené BDD pro manipulaci s množinami v kombinatorických problémech ", DAC '93: Sborník z 30. mezinárodní konference o Design Automation, 1993
Ch. Meinel, T. Theobald, “Algoritmy a datové struktury ve VLSI-Design: OBDD - základy a aplikace " Springer-Verlag, Berlín, Heidelberg, New York, 1998.
Minato, Shin-ichi. "Nulové potlačené BDD a jejich aplikace." https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/16895/1/IJSTTT3-2.pdf, Hokkaido University, květen 2001, https://eprints.lib.hokudai.ac.jp/dspace/bitstream/2115/16895/1/IJSTTT3-2.pdf.
Minato, Shin-ichi. "Nulové potlačené BDD pro manipulaci s množinami v kombinačních problémech." 1993, doi:https://pdfs.semanticscholar.org/9593/6223362a16a50de2959475d87aefe2a1fec7.pdf.
Bryant, Randal E. „Binární rozhodovací diagramy a další: Podpora technologií pro formální ověření.“ http://Repository.cmu.edu/Cgi/Viewcontent.cgi?Article=1245&Context=Compsci, Carnegie Mellon University, listopad 1995, repository.cmu.edu/cgi/viewcontent.cgi?article=1245&context=compsci.
Lynn, Ben. "ZDD." ZDDs - Introduction, Stanford University, 2005, crypto.stanford.edu/pbc/notes/zdd/.
Mishchenko, Alan. "Úvod do binárních rozhodovacích diagramů s nulovým potlačením." 5. února 2014, doi:https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd_.pdf.
Knuth, Donald E. The Art of Computer Programming, svazek 4. 22. prosince 2008.
externí odkazy
Minato, Shin-ichi. "Nulové potlačené BDD a jejich aplikace." https://Www.researchgate.net/Profile/Shin-ichi_Minato/Publication/37555760_Zero-suppressed_BDDs_and_their_applications/Links/02e7e52b85cd639cb5000000.Pdf Univerzita Hokkaido, květen 2001, www.researchgate.net/profile/Shin-ichi_Minato/publication/37555760_Zero-suppressed_BDDs_and_their_applications/links/02e7e52b85cd639cb5000000.pdf.
Minato, Shin-ichi. "Nulové potlačené BDD pro manipulaci s množinami v kombinačních problémech." 1993, doi:https://pdfs.semanticscholar.org/9593/6223362a16a50de2959475d87aefe2a1fec7.pdf.
Bryant, Randal E. „Binární rozhodovací diagramy a další: Podpora technologií pro formální ověření.“ http://Repository.cmu.edu/Cgi/Viewcontent.cgi?Article=1245&Context=Compsci, Carnegie Mellon University, listopad 1995, repository.cmu.edu/cgi/viewcontent.cgi?article=1245&context=compsci.
Lynn, Ben. "ZDD." ZDDs - Introduction, Stanford University, 2005, crypto.stanford.edu/pbc/notes/zdd/.
Alan Mishchenko, Alan. "Úvod do binárních rozhodovacích diagramů s nulovým potlačením." 5. února 2014, doi:https://people.eecs.berkeley.edu/~alanmi/publications/2001/tech01_zdd_.pdf.
Alan Mishchenko, Úvod do binárních rozhodovacích diagramů s nulovým potlačením
Donald Knuth, Zábava s nulovými potlačenými binárními rozhodovacími diagramy (ZDD) (video přednáška, 2008)
Minato Shin-ichi, Počítání cest v grafech (základy ZDD) (video ilustrace vytvořená na Miraikanu)