Algorithms for approximate FSM traversal

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Algorithms for approximate FSM traversal

Full text

Pdf (828 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 30th international Design Automation Conference table of contents

Dallas, Texas, United States

Pages: 25 - 30

Year of Publication: 1993

ISBN:0-89791-577-1

Authors

Hyunwoo Cho
Gary D. Hachtel
Enrico Macii
Bernard Plessier
Fabio Somenzi

Sponsors

EDAC : Electronic Design Automation Consortium
IEEE-CAS : Circuits & Systems
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 15, Downloads (12 Months): 21, Citation Count: 30

Additional Information:

references cited by index terms collaborative colleagues

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

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/157485.164555 What is a DOI?

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	O. Coudert, C. Berthet, J. C. Madre, "Verification of Sequential Machines Using Boolean Functional Vectors", IFIP Wo~'kshop on Applied Formal Me,hods, pp. 111-128, Nov. 1989.
	2	O. Coudert, J. C. Madre, "A Unified Framework for the Formal Verification of Sequential Circuits", ICCAD-90, pp. 126- 129, Nov. 1990.
	3	H. Touati, H. Savoj, B. Lin, B.. Brayton, A. Sangiovanni- Vincentelli, "Implicit Enumeration of Finite State Machines Using BDD's", ICCAD.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-137, 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	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]
	7	Karl S. Brace , Richard L. Rudell , Randal E. Bryant, Efficient implementation of a BDD package, Proceedings of the 27th ACM/IEEE conference on Design automation, p.40-45, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123222]
	8	H. Cho, F. Somenzi, "Sequential Logic Optimization Based on State Space Decomposition", EDAC.93, Feb. 1993.
	9	K. A. Bartlett, B.. Brayton, G. D. Hachtel, It. Jacoby, C. Morrison, 17,. Rudell, A. Sangiovanni-Vincentelli, A. Wang, "Multi-Level Logic Minimization Using Implicit Don't Cares", IEEE Transactions o~ CAD, Vol. CAD-7, No. 6, pp. 723-740, Jun. 1988.
	10	Hyunwoo Cho , Gary D. Hachtel , Fabio Somenzi, Redundancy Identification and Removal Based on Implicit State Enumeration, Proceedings of the 1991 IEEE International Conference on Computer Design on VLSI in Computer & Processors, p.77-80, October 14-16, 1991
	11	B. Lin, H.Touati, A.B.. Newton, "Don't Care Minimization of Multi-Level Sequential Logic Networks", ICCAD-90, pp. 414- 417, Nov. 1990.
	12	F. Brglez, D. Bryan, K. Ko~miSski, "CombinationalProfiles of Sequential Benchmark Circuits", ISCAS-89, pp. 1929-1934, May 1989.
	13	R. Drayton, It. Rudcll~ A. Sangiovanni-Vincentelli, A. Wang~ "MIS: A Multiple-Level Interactive Logic Optimization System", IEEE Tr~rns~rctions on CAD, Vol. CAD-6, No. 11, pp. 1062-1081, Nov. 1987.
	14	S. Yang, "Logic Synthesis and Optimization Benchmarks User Guide Version 3.0", Techrt~ca! 1"epo~'t, MCNC, Jan. 1991.

CITED BY 30

	Abelardo Pardo , Gary D. Hachtel, Incremental CTL model checking using BDD subsetting, Proceedings of the 35th annual conference on Design automation, p.457-462, June 15-19, 1998, San Francisco, California, United States
	Andreas Kuehlmann , Cornelis A. J. van Eijk, Combinational and sequential equivalence checking, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	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
	Pranav Ashar , Aarti Gupta , Sharad Malik, Using complete-1-distinguishability for FSM equivalence checking, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.4, p.569-590, October 2001
	C. A. J. van Eijk, Sequential equivalence checking without state space traversal, Proceedings of the conference on Design, automation and test in Europe, p.618-623, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Gianpiero Cabodi , Stefano Quer , Paolo Camurati, Computing subsets of equivalence classes for large FSMs, Proceedings of the conference on European design automation, p.288-293, September 18-22, 1995, Brighton, England
	Kavita Ravi , Fabio Somenzi, High-density reachability analysis, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.154-158, November 05-09, 1995, San Jose, California, United States
	Jörg Bormann , Jörg Lohse , Michael Payer , Gerd Venzl, Model checking in industrial hardware design, Proceedings of the 32nd ACM/IEEE conference on Design automation, p.298-303, June 12-16, 1995, San Francisco, California, United States
	Christoph Meinel , Fabio Somenzi , Thorsten Theobald, Linear sifting of decision diagrams, Proceedings of the 34th annual conference on Design automation, p.202-207, June 09-13, 1997, Anaheim, California, United States
	Pranav Ashar , Aarti Gupta , Sharad Malik, Using complete-1-distinguishability for FSM equivalence checking, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.346-353, November 10-14, 1996, San Jose, California, United States
	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
	David E. Long , Mahesh A. Iyer , Miron Abramovici, FILL and FUNI: algorithms to identify illegal states and sequentially untestable faults, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.3, p.631-657, July 2000
	Gianpiero Cabodi , P. Camurati , Stefano Quer, Symbolic exploration of large circuits with enhanced forward/backward traversals, Proceedings of the conference on European design automation, p.22-27, September 19-23, 1994, Grenoble, France
	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
	Alessandro Fin , Franco Fummi , Giovanni Perbellini, Soft-cores generation by instruction set analysis, Proceedings of the 14th international symposium on Systems synthesis, September 30-October 03, 2001, Montréal, P.Q., Canada
	Andreas Hett , Christoph Scholl , Bernd Becker, Distance driven finite state machine traversal, Proceedings of the 37th conference on Design automation, p.39-42, June 05-09, 2000, Los Angeles, California, United States
	Yih-Chih Chou , Youn-Long Lin, A 3-step approach for performance-driven whole-chip routing, Proceedings of the 2001 conference on Asia South Pacific design automation, p.187-191, January 2001, Yokohama, Japan
	Irith Pomeranz , Sudhakar M. Reddy, On Finding a Minimal Functional Description of a Finite-State Machine for Test Generation for Adjacent Machines, IEEE Transactions on Computers, v.49 n.1, p.88-94, January 2000
	Wolfgang Günther , Andreas Hett , Bernd Becker, Application of linearly transformed BDDs in sequential verification, Proceedings of the 2001 conference on Asia South Pacific design automation, p.91-96, January 2001, Yokohama, Japan
	R. I. Bahar , E. A. Frohm , C. M. Gaona , G. D. Hachtel , E. Macii , A. Pardo , F. Somenzi, Algebric Decision Diagrams and Their Applications, Formal Methods in System Design, v.10 n.2-3, p.171-206, April -May 1997
	Giampiero Cabodi , Paolo Camurati , Fulvio Corno , Paolo Prinetto , Matteo Sonza Reorda, The General Product Machine: a New Model for Symbolic FSM Traversal, Formal Methods in System Design, v.12 n.3, p.267-289, April 1, 1998
	Fabrizio Ferrandi , Franco Fummi , Donatella Sciuto, Test Generation and Testability Alternatives Exploration of Critical Algorithms for Embedded Applications, IEEE Transactions on Computers, v.51 n.2, p.200-215, February 2002
	Stefano Quer , Gianpiero Cabodi , Paolo Camurati , Luciano Lavagno , Ellen M. Sentovich , Robert K. Brayton, Verification of Similar FSMs by Mixing Incremental Re-encoding, Reachability Analysis, and Combinational Checks, Formal Methods in System Design, v.17 n.2, p.107-134, Oct. 2000
	Robert K. Brayton, The future of logic synthesis and verification, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Youpyo Hong , Peter A. Beerel, Symbolic reachability analysis of large finite state machines using don't cares, Proceedings of the conference on Design, automation and test in Europe, p.5-es, January 1999, Munich, Germany
	Chao Wang , Gary D. Hachtel , Fabio Somenzi, The Compositional Far Side of Image Computation, Proceedings of the 2003 IEEE/ACM international conference on Computer-aided design, p.334, November 09-13, 2003
	I. Pomeranz , S. M. Reddy, On the use of reset to increase the testability of interconnected finite-state machines, Proceedings of the 1997 European conference on Design and Test, p.554, March 17-20, 1997
	Irith Pomeranz , Sudhakar M. Reddy, On Test Generation for Interconnected Finite-State Machines - The Output Sequence Justification Problem, Proceedings of the 1996 European conference on Design and Test, p.380, March 11-14, 1996
	Ansuman Banerjee , Pallab Dasgupta , P. P. Chakrabarti, Auxiliary state machines + context-triggered properties in verification, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.13 n.4, p.1-31, September 2008
	Chen-Hsuan Lin , Chun-Yao Wang, Dependent latch identification in the reachable state space, Proceedings of the 2009 Conference on Asia and South Pacific Design Automation, January 19-22, 2009, Yokohama, Japan