ACM Portal
  Subscribe (Full Service)    Register (Limited Service, Free)    Login
  Search:   The ACM Digital Library   The Guide
  
ACM Home Page
Please provide us with feedback. Feedback
Algebraic decision diagrams and their applications
Full text PdfPdf (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): 9,   Downloads (12 Months): 51,   Citation Count: 76
Additional Information:

references   cited by   collaborative colleagues  

Tools and Actions: Review this Article  

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  76
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
S. Höreth, Compilation of optimized OBDD-algorithms, Proceedings of the conference on European design automation, p.152-157, September 1996, Geneva, Switzerland
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
Randal E. Bryant , Christoph Meinel, Ordered binary decision diagrams, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 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
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
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
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
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
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
Edmund M. Clarke , Bernd-Holger Schlingloff, Model checking, Handbook of automated reasoning, Elsevier Science Publishers B. V., Amsterdam, The Netherlands, 2001
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
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
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
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
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
Kee-Eung Kim , Thomas Dean, Solving factored MDPs using non-homogeneous partitions, Artificial Intelligence, v.147 n.1-2, p.225-251, July 2003
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
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
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
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
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
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
John Lafferty , Alexander Vardy, Ordered Binary Decision Diagrams and Minimal Trellises, IEEE Transactions on Computers, v.48 n.9, p.971-986, September 1999
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
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
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
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
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
Henrik Reif Andersen , Henrik Hulgaard, Boolean expression diagrams, Information and Computation, v.179 n.2, p.194-212, December 15, 2002
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Håkan L. S. Younes, Planning and execution with phase transitions, Proceedings of the 20th national conference on Artificial intelligence, p.1030-1035, July 09-13, 2005, Pittsburgh, Pennsylvania
Scott Sanner , Craig Boutilier, Practical solution techniques for first-order MDPs, Artificial Intelligence, v.173 n.5-6, p.748-788, April, 2009
Dipankar Das , P. P. Chakrabarti , Rajeev Kumar, Scenario-based timing verification of multiprocessor embedded applications, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.14 n.3, p.1-58, May 2009
Cédric Pralet , Gérard Verfaillie , Thomas Schiex, An algebraic graphical model for decision with uncertainties, feasibilities, and utilities, Journal of Artificial Intelligence Research, v.29 n.1, p.421-489, May 2007
Hyeong Seop Sim , Kee-Eung Kim , Jin Hyung Kim , Du-Seong Chang , Myoung-Wan Koo, Symbolic heuristic search value iteration for factored POMDPs, Proceedings of the 23rd national conference on Artificial intelligence, p.1088-1093, July 13-17, 2008, Chicago, Illinois
Wei Li , Pascal Poupart , Peter Van Beek, Exploiting causal independence using weighted model counting, Proceedings of the 23rd national conference on Artificial intelligence, p.337-343, July 13-17, 2008, Chicago, Illinois
Chenggang Wang , Saket Joshi , Roni Khardon, First order decision diagrams for relational MDPs, Journal of Artificial Intelligence Research, v.31 n.1, p.431-472, January 2008
Robert Mateescu , Rina Dechter , Radu Marinescu, AND/OR multi-valued decision diagrams (AOMDDs) for graphical models, Journal of Artificial Intelligence Research, v.33 n.1, p.465-519, September 2008
Mark Chavira , Adnan Darwiche, Compiling Bayesian networks using variable elimination, Proceedings of the 20th international joint conference on Artifical intelligence, p.2443-2449, January 06-12, 2007, Hyderabad, India
Hélène Fargier , Pierre Marquis, On valued negation normal form formulas, Proceedings of the 20th international joint conference on Artifical intelligence, p.360-365, January 06-12, 2007, Hyderabad, India
Chenggang Wang , Saket Joshi , Roni Khardon, First order decision diagrams for relational MDPs, Proceedings of the 20th international joint conference on Artifical intelligence, p.1095-1100, January 06-12, 2007, Hyderabad, India
Scott Sanner , David McAllester, Affine algebraic decision diagrams (AADDs) and their application to structured probabilistic inference, Proceedings of the 19th international joint conference on Artificial intelligence, p.1384-1390, July 30-August 05, 2005, Edinburgh, Scotland
Martin Sachenbacher , Brian C. Williams, Bounded search and symbolic inference for constraint optimization, Proceedings of the 19th international joint conference on Artificial intelligence, p.286-291, July 30-August 05, 2005, Edinburgh, Scotland
Saket Joshi , Kristian Kersting , Roni Khardon, Generalized first order decision diagrams for first order Markov decision processes, Proceedings of the 21st international jont conference on Artifical intelligence, p.1916-1921, July 11-17, 2009, Pasadena, California, USA
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

The ACM Portal is published by the Association for Computing Machinery. Copyright © 2009 ACM, Inc.
Terms of Usage   Privacy Policy   Code of Ethics   Contact Us

Useful downloads: Adobe Acrobat    QuickTime    Windows Media Player    Real Player