distr/cudd/doc/node1.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
   2
   3 <!--Converted with jLaTeX2HTML 2002-2-1 (1.70) JA patch-2.0
   4 patched version by:  Kenshi Muto, Debian Project.
   5 * modified by:  Shige TAKENO
   6 LaTeX2HTML 2002-2-1 (1.70),
   7 original version by:  Nikos Drakos, CBLU, University of Leeds
   8 * revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan
   9 * with significant contributions from:
  10   Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
  11 <HTML>
  12 <HEAD>
  13 <TITLE>Introduction</TITLE>
  14 <META NAME="description" CONTENT="Introduction">
  15 <META NAME="keywords" CONTENT="cuddIntro">
  16 <META NAME="resource-type" CONTENT="document">
  17 <META NAME="distribution" CONTENT="global">
  18
  19 <META NAME="Generator" CONTENT="jLaTeX2HTML v2002-2-1 JA patch-2.0">
  20 <META HTTP-EQUIV="Content-Style-Type" CONTENT="text/css">
  21
  22 <LINK REL="STYLESHEET" HREF="cuddIntro.css">
  23
  24 <LINK REL="next" HREF="node2.html">
  25 <LINK REL="previous" HREF="cuddIntro.html">
  26 <LINK REL="up" HREF="cuddIntro.html">
  27 <LINK REL="next" HREF="node2.html">
  28 </HEAD>
  29
  30 <BODY >
  31 <!--Navigation Panel-->
  32 <A NAME="tex2html85"
  33   HREF="node2.html">
  34 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
  35  SRC="icons/next.png"></A>
  36 <A NAME="tex2html81"
  37   HREF="cuddIntro.html">
  38 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
  39  SRC="icons/up.png"></A>
  40 <A NAME="tex2html75"
  41   HREF="cuddIntro.html">
  42 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
  43  SRC="icons/prev.png"></A>
  44 <A NAME="tex2html83"
  45   HREF="node8.html">
  46 <IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
  47  SRC="icons/index.png"></A>
  48 <BR>
  49 <B> Next:</B> <A NAME="tex2html86"
  50   HREF="node2.html">How to Get CUDD</A>
  51 <B> Up:</B> <A NAME="tex2html82"
  52   HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
  53 <B> Previous:</B> <A NAME="tex2html76"
  54   HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
  55  &nbsp; <B>  <A NAME="tex2html84"
  56   HREF="node8.html">Index</A></B>
  57 <BR>
  58 <BR>
  59 <!--End of Navigation Panel-->
  60
  61 <H1><A NAME="SECTION00010000000000000000"></A>
  62 <A NAME="sec:intro"></A>
  63 <BR>
  64 Introduction
  65 </H1>
  66
  67 <P>
  68 The CUDD package provides functions to manipulate Binary Decision
  69 Diagrams<A NAME="14"></A> (BDDs) [<A
  70  HREF="node7.html#BDD">5</A>,<A
  71  HREF="node7.html#BBR">3</A>],
  72 Algebraic Decision Diagrams<A NAME="16"></A> (ADDs)
  73 [<A
  74  HREF="node7.html#Bahar93">1</A>], and Zero-suppressed Binary Decision
  75 Diagrams<A NAME="18"></A> (ZDDs)
  76 [<A
  77  HREF="node7.html#Minato93">12</A>]. BDDs are used to represent
  78 switching<A NAME="20"></A> functions; ADDs are used to
  79 represent function from <IMG
  80  WIDTH="56" HEIGHT="35" ALIGN="MIDDLE" BORDER="0"
  81  SRC="img3.png"
  82  ALT="$\{0,1\}^n$"> to an arbitrary set.  ZDDs
  83 represent switching<A NAME="21"></A> functions like BDDs;
  84 however, they are much more efficient than BDDs when the functions to
  85 be represented are characteristic<A NAME="22"></A>
  86 functions of cube<A NAME="23"></A> sets, or in general, when the
  87 ON-set<A NAME="24"></A> of the function to be represented is
  88 very sparse. They are inferior to BDDs in other cases.
  89
  90 <P>
  91 The package provides a large set of operations on BDDs, ADDs, and
  92 ZDDs, functions to convert BDDs into ADDs or ZDDs and vice versa, and
  93 a large assortment of variable reordering<A NAME="25"></A> methods.
  94
  95 <P>
  96 The CUDD package can be used in three ways:
  97
  98 <UL>
  99 <LI>As a black box<A NAME="27"></A>.  In this case, the application
 100   program that needs to manipulate decision diagrams only uses the
 101   exported functions of the package. The rich set of functions
 102   included in the CUDD package allows many applications to be written
 103   in this way.  Section&nbsp;<A HREF="node3.html#sec:user">3</A> describes how to use the
 104   exported functions of the package. An application written in terms
 105   of the exported functions of the package needs not concern itself
 106   with the details of variable reordering<A NAME="29"></A>, which may
 107   take place behind the scenes.
 108 Click <A NAME="tex2html1"
 109   HREF="cuddExtAbs.html">here</A>
 110 for a list of the
 111   exported functions.
 112 </LI>
 113 <LI>As a clear box<A NAME="32"></A>. When writing a sophisticated
 114   application based on decision diagrams, efficiency often dictates
 115   that some functions be implemented as direct recursive manipulation
 116   of the diagrams, instead of being written in terms of existing
 117   primitive functions.  Section&nbsp;<A HREF="node4.html#sec:prog">4</A> explains how to add new
 118   functions to the CUDD package. It also details how to write a
 119   recursive function that can be interrupted by
 120   dynamic<A NAME="34"></A> variable reordering.
 121 Click <A NAME="tex2html2"
 122   HREF="cuddAllAbs.html">here</A>
 123 for a list of the
 124   exported and internal functions.
 125 </LI>
 126 <LI>Through an interface. Object-oriented languages like C++ and
 127   Perl5 can free the programmer from the burden of memory management.
 128   A C++ interface is included in the distribution of CUDD. It
 129   automatically frees decision diagrams that are no longer used by the
 130   application and overloads operators. Almost all the functionality
 131   provided by the CUDD exported functions is available through the C++
 132   interface, which is especially recommended for fast prototyping.
 133   Section&nbsp;<A HREF="node5.html#sec:cpp">5</A> explains how to use the interface. A Perl5
 134   interface also exists and is ditributed separately. (See
 135   Section&nbsp;<A HREF="node2.html#sec:getFriends">2.2</A>.) Some applications define their own
 136   interfaces. See for example Section&nbsp;<A HREF="node3.html#sec:sis-vis">3.17</A>.
 137 </LI>
 138 </UL>
 139 In the following, the reader is supposed to be familiar with the basic
 140 ideas about decision diagrams, as found, for instance, in [<A
 141  HREF="node7.html#BBR">3</A>].
 142
 143 <P>
 144 <HR>
 145 <!--Navigation Panel-->
 146 <A NAME="tex2html85"
 147   HREF="node2.html">
 148 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
 149  SRC="icons/next.png"></A>
 150 <A NAME="tex2html81"
 151   HREF="cuddIntro.html">
 152 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
 153  SRC="icons/up.png"></A>
 154 <A NAME="tex2html75"
 155   HREF="cuddIntro.html">
 156 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
 157  SRC="icons/prev.png"></A>
 158 <A NAME="tex2html83"
 159   HREF="node8.html">
 160 <IMG WIDTH="43" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="index"
 161  SRC="icons/index.png"></A>
 162 <BR>
 163 <B> Next:</B> <A NAME="tex2html86"
 164   HREF="node2.html">How to Get CUDD</A>
 165 <B> Up:</B> <A NAME="tex2html82"
 166   HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
 167 <B> Previous:</B> <A NAME="tex2html76"
 168   HREF="cuddIntro.html">CUDD: CU Decision Diagram</A>
 169  &nbsp; <B>  <A NAME="tex2html84"
 170   HREF="node8.html">Index</A></B>
 171 <!--End of Navigation Panel-->
 172 <ADDRESS>
 173 Fabio Somenzi
 174 2009-02-20
 175 </ADDRESS>
 176 </BODY>
 177 </HTML>