Algebraic decision diagrams and their applications

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algebraic decision diagrams and their applications

Full text

Pdf (531 KB)

Source

International Conference on Computer Aided Design archive
Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design table of contents

Santa Clara, California, United States

Pages: 188 - 191

Year of Publication: 1993

ISBN:0-8186-4490-7

Authors

R. Iris Bahar	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO
Erica A. Frohm	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO
Charles M. Gaona	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO
Gary D. Hachtel	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO
Enrico Macii	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO and Politecnico di Torino, Dip. di Automatic e Informatica, Torino, Italy 10129
Abelardo Pardo	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO
Fabio Somenzi	University of Colorado, Department of Electrical and Computer Engineering, Boulder, CO

Sponsors

IEEE-CS : Computer Society
SIGDA: ACM Special Interest Group on Design Automation

Publisher

IEEE Computer Society Press Los Alamitos, CA, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 31, Citation Count: 63

Additional Information:

references cited by collaborative colleagues peer to peer

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Randal E. Bryant, Graph-based algorithms for Boolean function manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, Aug. 1986 [doi>10.1109/TC.1986.1676819]
	2	O. Coudert , C. Berthet , J. C. Madre, Verification of synchronous sequential machines based on symbolic execution, Proceedings of the international workshop on Automatic verification methods for finite state systems, p.365-373, February 1990, Grenoble, France
	3	H. Touati, H. Savo}, B. Lin) R. Brayton, A. Sangiovanni- Vincentelli, "Implicit Enumeration of Finite State Machines Using BDD's'), ICCA.D-90, pp. 130-133, Nov. 1990.
	4	H. Cho, G. D. Hachtel, S. W. Jeong, B. Plessier) E. Schwarz, F. Somenzi, "ATPG Aspects of FSM Verification", ICCAD-90) pp. 134-1373 Nov. 1990.
	5	J. R. Burch , E. M. Clarke , K. L. McMillan , David L. Dill, Sequential circuit verification using symbolic model checking, Proceedings of the 27th ACM/IEEE conference on Design automation, p.46-51, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123223]
	6	Hyunwoo Cho , Gary D. Hachtel , Enrico Macii , Bernard Plessier , Fabio Somenzi, Algorithms for approximate FSM traversal, Proceedings of the 30th international conference on Design automation, p.25-30, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164555]
	7	Gary D. Hachtel , Fabio Somenzi, A symbolic algorithm for maximum flow in 0-1 networks, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.403-406, November 07-11, 1993, Santa Clara, California, United States
	8	E. M. Clarke , K. L. McMillan , X Zhao , M. Fujita , J. Yang, Spectral transforms for large boolean functions with applications to technology mapping, Proceedings of the 30th international conference on Design automation, p.54-60, June 14-18, 1993, Dallas, Texas, United States [doi>10.1145/157485.164569]
	9	E. M. Clarke, M. Fujita, P. C. McGeer, K. McMillan, J. Young, "Multi-Terminal Binary Decision Diagrams: An Efficient Data Structure for Matrix Representation'), ICCAD-93, Nov. 1993.
	10	F. M. Brown, Boolean Reasoning: The Logic o/ Boolean Equations, Kluwer Academic Publishers, 1990.
	11	G. Gustavson, "Efficient Algorithm to Perform Sparse Matrix Multiplication", IBM Technical Disclo.~ure Bulletin, Vol. 20, No. 3, pp. 1262-1264, Aug. 1977.
	12	Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
	13	I. S. Duff , Roger G. Grimes , John G. Lewis, Sparse matrix test problems, ACM Transactions on Mathematical Software (TOMS), v.15 n.1, p.1-14, March 1989 [doi>10.1145/62038.62043]
	14	S. Ross, A Fzrst Course zn Probability, Macmillan, 1988.
	15	R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States

CITED BY 63

	Balakrishna Kumthekar , In-Ho Moon , Fabio Somenzi, A symbolic algorithm for low-power sequential synthesis, Proceedings of the 1997 international symposium on Low power electronics and design, p.56-61, August 18-20, 1997, Monterey, California, United States
	Gary D. Hachtel , Fabio Somenzi, A symbolic algorithm for maximum flow in 0-1 networks, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.403-406, November 07-11, 1993, Santa Clara, California, United States
	Kundan Nepal , Hui-Yuan Song , R. Iris Bahar , Joel Grodstein, RESTA: a robust and extendable symbolic timing analysis tool, Proceedings of the 14th ACM Great Lakes symposium on VLSI, April 26-28, 2004, Boston, MA, USA
	Olaf Schröer , Ingo Wegener, The Theory of Zero-Suppressed BDDs and the Number of Knight‘s Tours, Formal Methods in System Design, v.13 n.3, p.235-253, Nov. 1998
	Gary D. Hachtel , Mariano Hermida , Abelardo Pardo , Massimo Poncino , Fabio Somenzi, Re-encoding sequential circuits to reduce power dissipation, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.70-73, November 06-10, 1994, San Jose, California, United States
	Dragan Jankovic , Radomir S. Stankovic , Rolf Drechsler, Decision Diagram Method for Calculation of Pruned Walsh Transform, IEEE Transactions on Computers, v.50 n.2, p.147-157, February 2001
	Shipra Panda , Fabio Somenzi , Bernard F. Plessier, Symmetry detection and dynamic variable ordering of decision diagrams, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.628-631, November 06-10, 1994, San Jose, California, United States
	Randal E. Bryant , Yirng-An Chen, Verification of arithmetic circuits with binary moment diagrams, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.535-541, June 12-16, 1995, San Francisco, California, United States
	Kee-Eung Kim , Thomas Dean, Solving factored MDPs using non-homogeneous partitions, Artificial Intelligence, v.147 n.1-2, p.225-251, July 2003
	Clayton B. McDonald , Randal E. Bryant, Symbolic timing simulation using cluster scheduling, Proceedings of the 37th conference on Design automation, p.254-259, June 05-09, 2000, Los Angeles, California, United States
	E. M. Clarke , M. Fujita , X. Zhao, Hybrid decision diagrams, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.159-163, November 05-09, 1995, San Jose, California, United States
	Shipra Panda , Fabio Somenzi, Who are the variables in your neighborhood, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.74-77, November 05-09, 1995, San Jose, California, United States
	Christoph Scholl , Bernd Becker , Thomas M. Weis, Word-level decision diagrams, WLCDs and division, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.672-677, November 08-12, 1998, San Jose, California, United States
	Christoph Scholl , Bernd Becker , Thomas Weis, On WLCDs and the Complexity of Word-Level Decision Diagrams—A Lower Bound for Division, Formal Methods in System Design, v.20 n.3, p.311-326, May 2002
	Clayton B. McDonald , Randal E. Bryant, Symbolic functional and timing verification of transistor-level circuits, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.526-530, November 07-11, 1999, San Jose, California, United States
	S. Höreth , R. Drechsler, Dynamic minimization of word-level decision diagrams, Proceedings of the conference on Design, automation and test in Europe, p.612-617, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Vasco Jerinić , Jan Langer , Ulrich Heinkel , Dietmar Müller, New methods and coverage metrics for functional verification, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Henrik Reif Andersen , Henrik Hulgaard, Boolean expression diagrams, Information and Computation, v.179 n.2, p.194-212, December 15, 2002
	Shin-Ichi Minato , F. Somenzi, Arithmetic Boolean Expression Manipulator Using BDDs, Formal Methods in System Design, v.10 n.2-3, p.221-242, April -May 1997
	Stefan Höreth , Rolf Drechsler, Formal verification of word-level specifications, Proceedings of the conference on Design, automation and test in Europe, p.11-es, January 1999, Munich, Germany
	Srilatha Manne , Abelardo Pardo , R. Iris Bahar , Gary D. Hachtel , Fabio Somenzi , Enrico Macii , Massimo Poncino, Computing the maximum power cycles of a sequential circuit, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.23-28, June 12-16, 1995, San Francisco, California, United States
	Paul Tafertshofer , Massoud Pedram, Factored Edge-Valued Binary Decision Diagrams, Formal Methods in System Design, v.10 n.2-3, p.243-270, April -May 1997
	Clayton B. McDonald , Randal E. Bryant, Computing logic-stage delays using circuit simulation and symbolic elmore analysis, Proceedings of the 38th conference on Design automation, p.283-288, June 2001, Las Vegas, Nevada, United States
	Randal E. Bryant , Christoph Meinel, Ordered binary decision diagrams, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Rune M. Jensen , Manuela M. Veloso , Randal E. Bryant, State-set branching: Leveraging BDDs for heuristic search, Artificial Intelligence, v.172 n.2-3, p.103-139, February, 2008
	Kaviraj Chopra , Sarma B. K. Vrudhula, Implicit pseudo boolean enumeration algorithms for input vector control, Proceedings of the 41st annual conference on Design automation, June 07-11, 2004, San Diego, CA, USA
	Luca Benini , Enrico Macii , Massimo Poncino, Telescopic units: increasing the average throughput of pipelined designs by adaptive latency control, Proceedings of the 34th annual conference on Design automation, p.22-27, June 09-13, 1997, Anaheim, California, United States
	Randal E. Bryant, Binary decision diagrams and beyond: enabling technologies for formal verification, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.236-243, November 05-09, 1995, San Jose, California, United States
	Jürgen Ruf , Thomas Kropf, Symbolic Verification and Analysis of Discrete Timed Systems, Formal Methods in System Design, v.23 n.1, p.67-108, July 2003
	Smita Krishnaswamy , George F. Viamontes , Igor L. Markov , John P. Hayes, Probabilistic transfer matrices in symbolic reliability analysis of logic circuits, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.1, p.1-35, January 2008
	Kanji Hirabayashi, A Method of Formal Verification of Cryptographic Circuits, Journal of Electronic Testing: Theory and Applications, v.13 n.3, p.321-322, Dec. 1998
	Marsha Chechik , Arie Gurfinkel , Benet Devereux , Albert Lai , Steve Easterbrook, Data structures for symbolic multi-valued model-checking, Formal Methods in System Design, v.29 n.3, p.295-344, November 2006
	Marsha Chechik , Benet Devereux , Steve Easterbrook , Arie Gurfinkel, Multi-valued symbolic model-checking, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.4, p.371-408, October 2003
	S. Höreth, Compilation of optimized OBDD-algorithms, Proceedings of the conference on European design automation, p.152-157, September 1996, Geneva, Switzerland
	Scott Sanner , Craig Boutilier, Practical solution techniques for first-order MDPs, Artificial Intelligence, v.173 n.5-6, p.748-788, April, 2009
	L. Benini , G. De Micheli , E. Macii , M. Poncino , R. Scarsi, Symbolic synthesis of clock-gating logic for power optimization of control-oriented synchronous networks, Proceedings of the 1997 European conference on Design and Test, p.514, March 17-20, 1997
	Kathi Fisler , Shriram Krishnamurthi , Leo A. Meyerovich , Michael Carl Tschantz, Verification and change-impact analysis of access-control policies, Proceedings of the 27th international conference on Software engineering, May 15-21, 2005, St. Louis, MO, USA
	C. Moraga , T. Sasao , R. Stanković, A Unifying Approach to Edge-valued and Arithmetic Transform Decision Diagrams, Automation and Remote Control, v.63 n.1, p.125-138, January 2002
	Natasa Miskov-Zivanov , Diana Marculescu, MARS-C: modeling and reduction of soft errors in combinational circuits, Proceedings of the 43rd annual conference on Design automation, July 24-28, 2006, San Francisco, CA, USA
	John Lafferty , Alexander Vardy, Ordered Binary Decision Diagrams and Minimal Trellises, IEEE Transactions on Computers, v.48 n.9, p.971-986, September 1999
	Hui Xu , Rob A. Rutenbar , Karem Sakallah, sub-SAT: a formulation for relaxed boolean satisfiability with applications in routing, Proceedings of the 2002 international symposium on Physical design, April 07-10, 2002, San Diego, CA, USA
	R. Iris Bahar , Gary D. Hachtel , Enrico Macii , Fabio Somenzi, A symbolic method to reduce power consumption of circuits containing false paths, Proceedings of the 1994 IEEE/ACM international conference on Computer-aided design, p.368-371, November 06-10, 1994, San Jose, California, United States
	Rolf Drechsler , Wolfgang Günther , Stefan Höreth, Minimization of word-level decision diagrams, Integration, the VLSI Journal, v.33 n.1, p.39-70, December 2002
	George F. Viamontes , Manoj Rajagopalan , Igor L. Markov , John P. Hayes, Gate-level simulation of quantum circuits, Proceedings of the 2003 conference on Asia South Pacific design automation, January 21-24, 2003, Kitakyushu, Japan
	Håkan L. S. Younes , Reid G. Simmons, Statistical probabilistic model checking with a focus on time-bounded properties, Information and Computation, v.204 n.9, p.1368-1409, September 2006
	Enrico Macii , Massimo Poncino, Predicting the functional complexity of combinational circuits by symbolic spectral analysis of Boolean functions, Proceedings of the conference on European design automation, p.294-299, September 18-22, 1995, Brighton, England
	Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Probabilistic analysis of large finite state machines, Proceedings of the 31st annual conference on Design automation, p.270-275, June 06-10, 1994, San Diego, California, United States
	Jürgen Ruf , Thomas Kropf, Analyzing real-time systems, Proceedings of the conference on Design, automation and test in Europe, p.243-249, March 27-30, 2000, Paris, France
	Pejman Lotfi-Kamran , Mohammad Hosseinabady , Hamid Shojaei , Mehran Massoumi , Zainalabedin Navabi, TED+: a data structure for microprocessor verification, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	A. Bogliolo , L. Benini , G. De Micheli, Characterization-free behavioral power modeling, Proceedings of the conference on Design, automation and test in Europe, p.767-773, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Patrick Vuillod , Luca Benini , Giovanni De Micheli, Generalized matching from theory to application, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.13-20, November 09-13, 1997, San Jose, California, United States
	P. Vuillod , L. Benini , G. De Micheli, Re-mapping for low power under tight timing constraints, Proceedings of the 1997 international symposium on Low power electronics and design, p.287-292, August 18-20, 1997, Monterey, California, United States
	Yunjian Jiang , Robert K. Brayton, Logic optimization and code generation for embedded control applications, Proceedings of the ninth international symposium on Hardware/software codesign, p.225-229, April 2001, Copenhagen, Denmark
	Ansaf Salleb-Aouissi , Christel Vrain, A Contribution to the Use of Decision Diagrams for Loading and Mining Transaction Databases, Fundamenta Informaticae, v.78 n.4, p.575-594, December 2007
	R. Iris Bahar , Erica A. Frohm , Charles M. Gaona , Gary D. Hachtel , Enrico Macii , Abelardo Pardo , Fabio Somenzi, Algebraic decision diagrams and their applications, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.188-191, November 07-11, 1993, Santa Clara, California, United States
	Alessandro Bogiolo , Luca Benini , Bruno Riccò, Power estimation of cell-based CMOS circuits, Proceedings of the 33rd annual conference on Design automation, p.433-438, June 03-07, 1996, Las Vegas, Nevada, United States
	Andreas Kuehlmann , Kenneth L. McMillan , Robert K. Brayton, Probabilistic state space search, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.574-579, November 07-11, 1999, San Jose, California, United States
	Jun Yuan , Kurt Shultz , Carl Pixley , Hillel Miller , Adnan Aziz, Automatic Vector Generation Using Constraints and Biasing, Journal of Electronic Testing: Theory and Applications, v.16 n.1-2, p.107-120, Feb/April 2000
	René Krenz , Elena Dubrova, Improved Boolean function hashing based on multiple-vertex dominators, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Edmund M. Clarke , Bernd-Holger Schlingloff, Model checking, Handbook of automated reasoning, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 2001
	Aiguo Xie , Peter A. Beerel, Efficient state classification of finite state Markov chains, Proceedings of the 35th annual conference on Design automation, p.605-610, June 15-19, 1998, San Francisco, California, United States
	Robert K. Brayton, The future of logic synthesis and verification, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Rolf Drechsler, Verifying integrity of decision diagrams, Integration, the VLSI Journal, v.32 n.1-3, p.61-75, November 2002

Collaborative Colleagues:

R. Iris Bahar: colleagues

Erica A. Frohm: colleagues

Charles M. Gaona: colleagues

Gary D. Hachtel: colleagues

Enrico Macii: colleagues

Abelardo Pardo: colleagues

Fabio Somenzi: colleagues

Peer to Peer - Readers of this Article have also read:

Data structures for quadtree approximation and compression Communications of the ACM 28, 9
Hanan Samet
A hierarchical single-key-lock access control using the Chinese remainder theorem Proceedings of the 1992 ACM/SIGAPP Symposium on Applied computing
Kim S. Lee , Huizhu Lu , D. D. Fisher
The GemStone object database management system Communications of the ACM 34, 10
Paul Butterworth , Allen Otis , Jacob Stein
Putting innovation to work: adoption strategies for multimedia communication systems Communications of the ACM 34, 12
Ellen Francik , Susan Ehrlich Rudman , Donna Cooper , Stephen Levine
An intelligent component database for behavioral synthesis Proceedings of the 27th ACM/IEEE Design Automation Conference on
Gwo-Dong Chen , Daniel D. Gajski

Adobe Acrobat

QuickTime

Windows Media Player

Real Player