New ideas for solving covering problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

New ideas for solving covering problems

Full text

Pdf (227 KB)

Source

Annual ACM IEEE Design Automation Conference archive
Proceedings of the 32nd annual ACM/IEEE Design Automation Conference table of contents

San Francisco, California, United States

Pages: 641 - 646

Year of Publication: 1995

ISBN:0-89791-725-1

Authors

Olivier Coudert	Synopsys, 700 East Middlefield Rd., Mountain View, CA
Jean Chritophe Madre	Synopsys, 700 East Middlefield Rd., Mountain View, CA

Sponsors

EDAC : Electronic Design Automation Consortium
SIGDA: ACM Special Interest Group on Design Automation

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 15, Citation Count: 22

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/217474.217603 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	Robert King Brayton , Alberto L. Sangiovanni-Vincentelli , Curtis T. McMullen , Gary D. Hachtel, Logic Minimization Algorithms for VLSI Synthesis, Kluwer Academic Publishers, Norwell, MA, 1984
	2	R. K. Brayton, F. Somenzi, "An Exact Minimizer for Boolean Relation", in Proc. of ICCAD'89, pp. 1062- 1081, November 1989
	3	Olivier Coudert, Two-level logic minimization: an overview, Integration, the VLSI Journal, v.17 n.2, p.97-140, Oct. 1994 [doi>10.1016/0167-9260(94)00007-7]
	4	J. F. Gimpel, "A Reduction Technique for Prime Implicant Tables", in IEEE Trans. on Elec. Comp., 14, pp. 535-541, June 1965.
	5	A. Grasselli, F. Luccio, "A Method for Minimizing the Number of Internal States in Incompletely Sequential Networks", in IEEE Trans. on Elec. Comp., 14, pp. 350-359, June 1965.
	6	R. W. House, D. W. Stevens, "A New Rule for Reducing CC Tables", in IEEE Trans. on Comp., 19, pp. 1108-1111, November 1970.
	7	Zvi Kohavi , Richard W. Hamming , Edward A. Feigenbaum, Switching and Finite Automata Theory: Computer Science Series, McGraw-Hill Higher Education, 1990
	8	K. Keutzer, DAGON: technology binding and local optimization by DAG matching, Proceedings of the 24th ACM/IEEE conference on Design automation, p.341-347, June 28-July 01, 1987, Miami Beach, Florida, United States [doi>10.1145/37888.37940]
	9	E. L. Jr. McCluskey, "Minimization of Boolean Functions", in Bell Sys. Tech. Jour., 35, pp. 1417-1444, April 1959.
	10	W. V. O. Quine, "A Way to Simplify Truth Functions", in Am. Math. Monthly, 62, pp. 627-631, 1955.
	11	W. V. O. Quine, "On Cores and Prime Implicants of Truth Functions", in Am. Math. Monthly, 66, pp. 755-760, 1959.
	12	J. Rho, G. I-Iachtel, F. Somenzi, R. Jacoby, "Exact and Heuristics Minimization of Incompletely Specified Finite State Machines", in Proc. of EDAC'90, Febrary 1990.
	13	S. Robinson, R. House, "Gimpel's Reduction Technique Extended to the Covering Problem With Costs", in IEEE Trans. on Elec. Comp., 16, pp. 509- 514, August 1967.
	14	R. L. Rudell, A. L. Sangiovanni-Vincentelli, "Multiple Valued Minimization for PLA Optimization", in IEEE Trans. on CAD, 6-5, pp. 727-750, Sep. 1987.
	15	Richard L. Rudell , Alberto Sangiovanni-Vincentelli, Logic synthesis for vlsi design, 1989
	16	S. Yang, Logic Synthesis and Optimization Benchmarks User Guide, Microelectronics Center of North Carolina, January 1991.

CITED BY 22

	Vasco M. Manquinho , João Marques-Silva, On using satisfiability-based pruning techniques in covering algorithms, Proceedings of the conference on Design, automation and test in Europe, p.356-363, March 27-30, 2000, Paris, France
	Jorge M. Pena , Arlindo L. Oliveira, A new algorithm for the reduction of incompletely specified finite state machines, Proceedings of the 1998 IEEE/ACM international conference on Computer-aided design, p.482-489, November 08-12, 1998, San Jose, California, United States
	C.-J. Shi , J. A. Brzozowski, Cluster-cover: a theoretical framework for a class of VLSI-CAD optimization problems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.76-107, Jan. 1998
	Olivier Coudert , Tsutomu Sasao, Two-level logic minimization, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Robert M. Fuhrer , Steven M. Nowick, OPTIMIST: state minimization for optimal 2-level logic implementation, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.308-315, November 09-13, 1997, San Jose, California, United States
	Stan Liao , Srinivas Devadas, Solving covering problems using LPR-based lower bounds, Proceedings of the 34th annual conference on Design automation, p.117-120, June 09-13, 1997, Anaheim, California, United States
	Evguenii I. Goldberg , Luca P. Carloni , Tiziano Villa , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Negative thinking by incremental problem solving: application to unate covering, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.91-98, November 09-13, 1997, San Jose, California, United States
	J. Van Praet , D. Lanneer , W. Geurts , G. Goossens, Processor modeling and code selection for retargetable compilation, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.6 n.3, p.277-307, July 2001
	Robert M. Fuhrer , Steven M. Nowick, OPTIMISTA: state minimization of asynchronous FSMs for optimum output logic, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.7-13, November 07-11, 1999, San Jose, California, United States
	S. Liao , K. Keutzer , S. Tjiang , S. Devadas, A new viewpoint on code generation for directed acyclic graphs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.3 n.1, p.51-75, Jan. 1998
	Olivier Coudert, On solving covering problems, Proceedings of the 33rd annual conference on Design automation, p.197-202, June 03-07, 1996, Las Vegas, Nevada, United States
	Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Readings in hardware/software co-design, Kluwer Academic Publishers, Norwell, MA, 2001
	Soha Hassoun , Carolyn McCreary, Regularity extraction via clan-based structural circuit decomposition, Proceedings of the 1999 IEEE/ACM international conference on Computer-aided design, p.414-419, November 07-11, 1999, San Jose, California, United States
	Stan Liao , Srinivas Devadas , Kurt Keutzer , Steve Tjiang, Instruction selection using binate covering for code size optimization, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.393-399, November 05-09, 1995, San Jose, California, United States
	Jesse Whittemore , Joonyoung Kim , Karem Sakallah, SATIRE: a new incremental satisfiability engine, Proceedings of the 38th conference on Design automation, p.542-545, June 2001, Las Vegas, Nevada, United States
	Stan Liao , Srinivas Devadas , Kurt Keutzer, A text-compression-based method for code size minimization in embedded systems, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.1, p.12-38, Jan. 1999
	Xiao Yu Li , Matthias F. Stallmann , Franc Brglez, Effective bounding techniques for solving unate and binate covering problems, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Inês Lynce , João P. Marques-Silva, An Overview of Backtrack Search Satisfiability Algorithms, Annals of Mathematics and Artificial Intelligence, v.37 n.3, p.307-326, March 2003
	Vasco M. Manquinho , João P. Marques-Silva, Satisfiability-Based Algorithms for Boolean Optimization, Annals of Mathematics and Artificial Intelligence, v.40 n.3-4, p.353-372, March 2004
	Zhaohui Fu , Sharad Malik, Solving the minimum-cost satisfiability problem using SAT based branch-and-bound search, Proceedings of the 2006 IEEE/ACM international conference on Computer-aided design, November 05-09, 2006, San Jose, California
	Sridhar Dasika , Sarma Vrudhula , Kaviraj Chopra , R. Srinivasan, A Framework for Battery-Aware Sensor Management, Proceedings of the conference on Design, automation and test in Europe, p.20962, February 16-20, 2004
	Tsutomu Sasao, On the numbers of variables to represent sparse logic functions, Proceedings of the 2008 IEEE/ACM International Conference on Computer-Aided Design, November 10-13, 2008, San Jose, California