Algorithms for discrete function manipulation

Arvind Srinivasan, Timothy Kam, Sharad Malik, Robert K. Brayton

Research output: Chapter in Book/Report/Conference proceedingConference contribution

154 Scopus citations

Abstract

An investigation was made of the analogous graph structure for representing and manipulating discrete variable problems. The authors define the multi-valued decision diagram (MDD), analyze its properties (in particular prove a strong canonical form) and provide algorithms for combining and manipulating MDDs. They give a method for mapping an MDD into an equivalent BDD (binary decision diagrams) which allows them to provide a highly efficient implementation using the previously developed BDD packages. A direct implementation of the MDD structure has also been carried out, but this initial implementation has not yet been tuned to the same extent as the BDDs to allow a reasonable comparison to be made. The authors have used the mapping to BDDs to provide an initial understanding of the limits on the sizes of real problems that can be executed. The results are encouraging.

Original languageEnglish (US)
Title of host publication1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers
PublisherPubl by IEEE
Pages92-95
Number of pages4
ISBN (Print)0818620552
StatePublished - Dec 1 1990
Externally publishedYes
Event1990 IEEE International Conference on Computer-Aided Design - ICCAD-90 - Santa Clara, CA, USA
Duration: Nov 11 1990Nov 15 1990

Publication series

Name1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers

Other

Other1990 IEEE International Conference on Computer-Aided Design - ICCAD-90
CitySanta Clara, CA, USA
Period11/11/9011/15/90

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Fingerprint Dive into the research topics of 'Algorithms for discrete function manipulation'. Together they form a unique fingerprint.

  • Cite this

    Srinivasan, A., Kam, T., Malik, S., & Brayton, R. K. (1990). Algorithms for discrete function manipulation. In 1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers (pp. 92-95). (1990 IEEE International Conference on Computer-Aided Design. Digest of Technical Papers). Publ by IEEE.