Call Us 07766496223

Similar Articles

facebooktwitter





Latest Videos

Feed not found.

Log In or Register to Comment Without Captcha

Latest Forum Posts

Latest Set Theory Notes

Latest Blog Posts

Understand? Take a Test.

Constructing ZDDs

Given a family  
\[F\]
  of sets, we can find its ZDD as follows.
  • If  
    \[F = \emptyset\]
      (
    \[F\]
      is empty) return  
    \[\bot\]
     . If  
    \[F = \epsilon\]
      (
    \[F\]
      contains only the empty set) then return  
    \[\top\]
     .
  • Find the smallest element  
    \[v\]
      amongst all elements in all sets of  
    \[F\]
     . Create a node  
    \[v\]
     .
  • Let  
    \[F_0\]
      be the family of all sets in  
    \[F\]
      not containing  
    \[v(\]
    , that is,  
    \[; F_0 = \{ \alpha : \alpha \in F, v \notin \alpha \}\]
    . Recursively construct the ZDD for  
    \[F_0(\]
    , and connect the LO edge from  
    \[v\]
      to the root of  
    \[F_0\]
     .
  • Let  
    \[F_1\]
      be the family resulting from taking all sets in  
    \[F\]
      that contain  
    \[v\]
      and then removing  
    \[v\]
      from each set:  
    \[ F_1 = \{ \alpha\setminus\{v\} : \alpha \in F, v \in \alpha \} \]
    . Recursively construct the ZDD for  
    \[F_1\]
    , and connect the HI edge from  
    \[v\]
      to the root of  
    \[F_1\]
     .
  • Look for identical nodes (same label, same LO desination and same HI destination) and combine them.
    • Some families have special properties allowing their ZDDs to be immediately constructed. In a universe of size  
    \[n\]
    , consider for example the family of all sets of size  
    \[k\]
      which we denote  
    \[S_k(\{1,...,n\})\]
     . The ZDD of  
    \[S_2(\{1,2,3\}) = \{ \{1,2\}, \{2,3\}, \{1,3\}\}\]
      is the following:

    con1.png

    The ZDD of  
    \[S_k(\{1,...,n\})\]
      turns out to be easy to describe (exercise).
    Here are some more examples. Let  
    \[U = \{1, ..., 6\}\]
      and  
    \[S = \{2,3,5\}\]
     . The ZDD of all subsets of  
    \[U\]
      containing exactly one element of  
    \[S\]
      is:

    con2.png

    The ZDD of all sets containing at least one element of  
    \[S\]
      is:

    con3.png

    The ZDD of all sets containing at most one element of  
    \[S\]
      is:

    con4.png

    These 3 examples are readily generalized. Each can be viewed as a ZDD of all sets that branches off at the smallest element of  
    \[S(\]
    , before joining the main branch again after the largest element of  
    \[S\]
      has been handled.