Algebraic Decision Diagrams and their Applications

R. I. Bahar, E. Frohm, C. Gaona, G. Hachtel, E. Macii, A. Pardo and F. Somenzi

Proceedings of the International Conference on Computer Aided Design, November 1993.

Abstract

In this paper we present theory and experimental results on the Algebraic Decision Diagrams. These diagrams, also known as Multi-Terminal Decision diagrams, extend BDD's by allowing values from an arbitrary finite domain to be associated with the terminal nodes of the diagram. We present a treatment founded in boolean algebras and discuss algorithms and results in several areas of application: matrix multiplication, shortest path algorithms, Gaussian Elimination, pivoting in numerical linear algebra, and probabilistic analysis of finite state machines. The relation of our new algorithms to prior work is thoroughly discussed: in particular, we have compared our results in numerical linear algebra to those of several alternative approaches and we have analyzed the relation between our shortest path algorithms and recent work in FSM verification. We discuss the relevance of our findings and point to directions for future work.

Click here to download the compressed postscript version.

BibTeX Entry

@INPROCEEDINGS { Bahar93 ,
        ADDRESS = "Santa Clara, CA" ,
        AUTHOR = "R. I. Bahar and E. A. Frohm and C. M. Gaona and G. D. Hachtel and E. Macii and A. Pardo and F. Somenzi" ,
        BOOKTITLE = "Proceedings of the International Conference on Computer-Aided Design" 
        MONTH =   nov  ,
        PAGES = "188-191" ,
        TITLE = "Algebraic Decision Diagrams and their Applications" ,
        YEAR = "1993"
        }
Return to the home page