BIB-VERSION:: CS-TR-v2.0
          ID:: SBCS//stark/ldd.pdf
       ENTRY:: April 1, 2004
ORGANIZATION:: State University of New York at Stony Brook, Computer Science
       TITLE:: Linear Decision Diagrams
        TYPE:: Technical Report
      AUTHOR:: Stark, Eugene W. and Song, Wenxin
     CONTACT:: Eugene W. Stark, Department of Computer Science,
                   SUNY at Stony Brook, Stony Brook, NY 11794-4400
                   Tel: 631-632-8444 <stark@cs.sunysb.edu>
        DATE:: April 1, 2004
   RETRIEVAL:: HTTP from BSD7.CS.SUNYSB.EDU with the URL
		   http://bsd7.cs.sunysb.edu/~stark/REPORTS/ldd.abstract

ABSTRACT::

We introduce *linear decision diagrams* (LDDs) as a special class of
linear representations of formal power series.  LDDs can be seen as a
generalization of some previously proposed structures, such as MTBDDs
and matrix diagrams, that have seen successful application in the
compact representation of Markov models with large state spaces.
Besides providing some possibilities for additional compression, LDDs
have an interesting and useful reversibility property that is not
shared by previously considered BDD variants.  In addition, LDDs have
the advantage that most LDD operations can be performed without any
assumption that the arguments are fully reduced or ``canonical.''
This suggests the possibility of using multiple reduction heuristics
that trade off reduction ``strength'' for computation cost.  We
present some experimental results that compare the sizes of MTBDD and
LDD representations for rate matrices obtained from some standard
benchmark examples.