page_title: Zero-suppressed decision diagram
section_title: Representing a family of sets
hierarchical_section_title: Zero-suppressed decision diagram / Definitions / Representing a family of sets
caption_attribution_description: English: how to represent a family in ZDD
context_page_description: A zero-suppressed decision diagram is a particular kind of binary decision diagram with fixed variable ordering. This data structure provides a canonically compact representation of sets, particularly suitable for certain combinatorial problems. Recall the OBDD reduction strategy i.e. a node is removed from the decision tree if both out-edges point to the same node. In contrast, a node in a ZDD is removed if its positive edge points to the terminal node 0. This provides an alternative strong normal form, with improved compression of sparse sets. It is based on a reduction rule devised by Shin-ichi Minato in 1993.
context_section_description: Let F be a ZDD. Let v be its root node. Then:
  1.	If v = ⊥ , then there can be no other nodes, and F represents Ø, the empty family.
  2.	If v = ⊤, then there can be no other nodes, and F represents the family containing just the empty set { Ø }. We call this a unit family, and denote it by .
  3.	If v has two children. Let v0 be the LO node, and v1 be the HI node. Let Fi be the family represented by the ZDD rooted at vi, which can be shown by proof of induction. Then F represents the family
  One may represent the LO branch as the sets in F that don't contain v:
  And the HI branch as the sets in F that do contain v:
caption: Figure 4: 
    
      
        
          {
          ∅
          }
          ∪
          {
          ∅
          ∪
          {
          2
          }
          }
          =
          {
          ∅
          ,
          {
          2
          }
          }
        
      
      {\displaystyle \{\emptyset \}\cup \{\emptyset \cup \{2\}\}=\{\emptyset ,\{2\}\}}
exif: {}