Zero-suppressed BDDs for set manipulation in combinatorial problems

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Zero-suppressed BDDs for set manipulation in combinatorial problems

Full text

Pdf (647 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: 272 - 277

Year of Publication: 1993

ISBN:0-89791-577-1

Author

Shin-ichi Minato

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): 25, Downloads (12 Months): 110, Citation Count: 58

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.164890 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	S. B. Akers: "Binary Decision Diagrams", IEEE Trans. Comput., pp. 509-516, 1978
	2	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]
	3	M. Fujita, ~I. Fujisawa and n. Kawato: "Evaluation and Improvement of Boolean Comparison Method Based on Binary Decision Diagrams", Proc. IEEE ICCAD'88, pp. 2-5, 1988
	4	Rhonda Kay Gaede , Don E. Ross , M. Ray Mercer , Kenneth M. Butler, CATAPULT: concurrent automatic testing allowing parallelization and using limited topology, Proceedings of the 25th ACM/IEEE conference on Design automation, p.597-600, June 12-15, 1988, Atlantic City, New Jersey, United States
	5	N. Takahashi, n. Ishiura and S. Yajima: "Fault Simulation for Multiple Faults Using Shared BDD Representation of Fault Sets", Proc. IEEE ICCAD'90, pp. 550-553~ 1991
	6	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]
	7	O. Coudert , J. C. Madre, Implicit and incremental computation of primes and essential primes of Boolean functions, Proceedings of the 29th ACM/IEEE conference on Design automation, p.36-39, June 08-12, 1992, Anaheim, California, United States
	8	Bill Lin and Fabio Somenzi: "Minimization of Symbolic Relations", Proc. IEEE ICCAD'90, pp. 88-91, (1990).
	9	Shin-ichi Minato , Nagisa Ishiura , Shuzo Yajima, Shared binary decision diagram with attributed edges for efficient Boolean function manipulation, Proceedings of the 27th ACM/IEEE conference on Design automation, p.52-57, June 24-27, 1990, Orlando, Florida, United States [doi>10.1145/123186.123225]
	10	Masahiro Fujita , Yusuke Matsunaga , Taeko Kakuda, On variable ordering of binary decision diagrams for the application of multi-level logic synthesis, Proceedings of the conference on European design automation, February 25-28, 1991, Amsterdam, The Netherlands
	11	Heh-Tyan Liaw , Chen-Shang Lin, On the OBDD-Representation of General Boolean Functions, IEEE Transactions on Computers, v.41 n.6, p.661-664, June 1992 [doi>10.1109/12.144618]
	12	O. Coudert and J. C. Madre: "A New implicit Graph Based Prime and Essential Prime Computation Technique", Proc. International Symposium on Logic Synthesis and Microprocessor Architecture (ISKIT 92, Japan), pp. 125-131, 1992.
	13	S. Minato: 'Fast Generation of Irredundant Sumof-Products Forms from Binary Decision Diagrams', Proceedings of the Synthesis and Simulation Meeting and International Interchange (SASIMI'92, Japan), 1992, pp. 64-73

CITED BY 58

	Luca Benini , Giovanni De Micheli , Enrico Macii , Massimo Poncino , Stefano Quer, System-level power optimization of special purpose applications: the beach solution, Proceedings of the 1997 international symposium on Low power electronics and design, p.24-29, August 18-20, 1997, Monterey, 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
	Huey-Yih Wang , Robert K. Brayton, Permissible observability relations in FSM networks, Proceedings of the 31st annual conference on Design automation, p.677-683, June 06-10, 1994, San Diego, California, United States
	Amit Narayan , Jawahar Jain , M. Fujita , A. Sangiovanni-Vincentelli, Partitioned ROBDDs—a compact, canonical and efficiently manipulable representation for Boolean functions, Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design, p.547-554, November 10-14, 1996, San Jose, California, United States
	Tony Stornetta , Forrest Brewer, Implementation of an efficient parallel BDD package, Proceedings of the 33rd annual conference on Design automation, p.641-644, June 03-07, 1996, Las Vegas, Nevada, 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
	Fadi A. Aloul , Brian D. Sierawski , Karem A. Sakallah, Satometer:: how much have we searched?, Proceedings of the 39th conference on Design automation, June 10-14, 2002, New Orleans, Louisiana, USA
	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
	C.-J. Richard Shi , Xiangdong Tan, Symbolic analysis of large analog circuits with determinant decision diagrams, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.366-373, November 09-13, 1997, San Jose, California, United States
	Olivier Coudert, Doing two-level logic minimization 100 times faster, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.112-121, January 22-24, 1995, San Francisco, California, United States
	Shin-ichi Minato, Calculation of unate cube set algebra using zero-suppressed BDDs, Proceedings of the 31st annual conference on Design automation, p.420-424, June 06-10, 1994, San Diego, California, United States
	Rolf Drechsler , Bernd Becker , Michael Theobald, Fast OFDD based minimization of fixed polarity Reed-Muller expressions, Proceedings of the conference on European design automation, p.2-7, September 19-23, 1994, Grenoble, France
	Roberto Cordone , Fabrizio Ferrandi , Donatella Sciuto , Roberto Wolfler Calvo, An efficient heuristic approach to solve the unate covering problem, Proceedings of the conference on Design, automation and test in Europe, p.364-371, March 27-30, 2000, Paris, France
	Amit Narayan , Adrian J. Isles , Jawahar Jain , Robert K. Brayton , Alberto L. Sangiovanni-Vincentelli, Reachability analysis using partitioned-ROBDDs, Proceedings of the 1997 IEEE/ACM international conference on Computer-aided design, p.388-393, November 09-13, 1997, San Jose, 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
	R. Glenn Wood , Rob A. Rutenbar, FPGA routing and routability estimation via Boolean satisfiability, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.119-125, February 09-11, 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
	Jeffery P. Hansen , Masatoshi Sekine, Synthesis by spectral translation using Boolean decision diagrams, Proceedings of the 33rd annual conference on Design automation, p.248-253, June 03-07, 1996, Las Vegas, Nevada, United States
	Alan Mishchenko , Robert Brayton, Simplification of non-deterministic multi-valued networks, Proceedings of the 2002 IEEE/ACM international conference on Computer-aided design, p.557-562, November 10-14, 2002, San Jose, California
	David A. Plaisted , Armin Biere , Yunshan Zhu, A satisfiability procedure for quantified boolean formulae, Discrete Applied Mathematics, v.130 n.2, p.291-328, 15 August 2003
	Chu-Min Li, Equivalent literal propagation in the DLL procedure, Discrete Applied Mathematics, v.130 n.2, p.251-276, 15 August 2003
	Enrico Macii , Massoud Pedram , Fabio Somenzi, High-level power modeling, estimation, and optimization, Proceedings of the 34th annual conference on Design automation, p.504-511, June 09-13, 1997, Anaheim, 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
	Ondřej Lhoták , Laurie Hendren, Jedd: a BDD-based relational extension of Java, ACM SIGPLAN Notices, v.39 n.6, May 2004
	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
	Bernd Becker , Rolf Drechsler , Michael Theobald, On the Expressive Power of OKFDDs, Formal Methods in System Design, v.11 n.1, p.5-21, July 1997
	Rolf Drechsler , Michael Theobald , Bernd Becker, Fast OFDD-Based Minimization of Fixed Polarity Reed-Muller Expressions, IEEE Transactions on Computers, v.45 n.11, p.1294-1299, November 1996
	David McAllester , Michael Collins , Fernando Pereira, Case-factor diagrams for structured probabilistic modeling, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.382-391, July 07-11, 2004, Banff, Canada
	Kameshwar Chandrasekar , Michael S. Hsiao, Forward image computation with backtracing ATPG and incremental state-set construction, Proceedings of the 15th ACM Great Lakes symposium on VLSI, April 17-19, 2005, Chicago, Illinois, USA
	Domagoj Babić , Jesse Bingham , Alan J. Hu, Efficient SAT solving: beyond supercubes, Proceedings of the 42nd annual conference on Design automation, June 13-17, 2005, San Diego, California, USA
	Kuo-Hua Wang , Jia-Hung Chen, K-disjointness paradigm with application to symmetry detection for incompletely specified functions, Proceedings of the 2005 conference on Asia South Pacific design automation, January 18-21, 2005, Shanghai, China
	Robert K. Brayton, The future of logic synthesis and verification, Logic Synthesis and Verification, Kluwer Academic Publishers, Norwell, MA, 2001
	Neil Kettle , Andy King, An anytime symmetry detection algorithm for ROBDDs, Proceedings of the 2006 conference on Asia South Pacific design automation, January 24-27, 2006, Yokohama, Japan
	Anna Bernasconi , Valentina Ciriani , Rolf Drechsler , Tiziano Villa, Efficient minimization of fully testable 2-SPP networks, Proceedings of the conference on Design, automation and test in Europe: Proceedings, March 06-10, 2006, Munich, Germany
	Saravanan Padmanaban , Spyros Tragoudas, Implicit grading of multiple path delay faults, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.11 n.2, p.346-361, April 2006
	Kyriakos Christou , Maria K. Michael , Spyros Tragoudas, On the Use of ZBDDs for Implicit and Compact Critical Path Delay Fault Test Generation, Journal of Electronic Testing: Theory and Applications, v.24 n.1-3, p.203-222, June 2008
	Robert Clarisó , Jordi Cortadella, The octahedron abstract domain, Science of Computer Programming, v.64 n.1, p.115-139, January, 2007
	Elsa Loekito , James Bailey, Fast mining of high dimensional expressive contrast patterns using zero-suppressed binary decision diagrams, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA
	Sungroh Yoon , Christine Nardini , Luca Benini , Giovanni De Micheli, Discovering Coherent Biclusters from Gene Expression Data Using Zero-Suppressed Binary Decision Diagrams, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.2 n.4, p.339-354, October 2005
	K. Lampka , M. Siegle, Analysis of Markov reward models using zero-suppressed multi-terminal BDDs, Proceedings of the 1st international conference on Performance evaluation methodolgies and tools, October 11-13, 2006, Pisa, Italy
	Walter Binder , Ion Constantinescu , Boi Faltings, Efficient Service Composition Using Zero-Suppressed Reduced Ordered Binary Decision Diagrams, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.587-593, December 18-22, 2006
	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
	Doron B. Motter , Jarrod A. Roy , Igor L. Markov, Resolution cannot polynomially simulate compressed-BFS, Annals of Mathematics and Artificial Intelligence, v.44 n.1-2, p.121-156, May 2005
	F. Corno , P. Prinetto , M. Sonza Reorda, Using symbolic techniques to find the maximum clique in very large sparse graphs, Proceedings of the 1995 European conference on Design and Test, p.320, March 06-09, 1995
	Saravanan Padmanaban , Spyros Tragoudas, Non-Enumerative Path Delay Fault Diagnosis, Proceedings of the conference on Design, Automation and Test in Europe, p.10322, March 03-07, 2003
	I. Radivojevic , F. Brewer, On applicability of symbolic techniques to larger scheduling problems, Proceedings of the 1995 European conference on Design and Test, p.48, March 06-09, 1995
	S. Minato, Implicit manipulation of polynomials using zero-suppressed BDDs, Proceedings of the 1995 European conference on Design and Test, p.449, March 06-09, 1995
	O. Coudert, Solving Graph Optimization Problems with ZBDDs, Proceedings of the 1997 European conference on Design and Test, p.224, March 17-20, 1997
	David McAllester , Michael Collins , Fernando Pereira, Case-factor diagrams for structured probabilistic modeling, Journal of Computer and System Sciences, v.74 n.1, p.84-96, February, 2008
	Elsa Loekito , James Bailey, Are zero-suppressed binary decision diagrams good for mining frequent patterns in high dimensional datasets?, Proceedings of the sixth Australasian conference on Data mining and analytics, December 03-04, 2007, Gold Coast, Australia
	K. Lampka , S. Harwarth , M. Siegle, Can matrix-layout-independent numerical solvers be efficient?: implementing the Moebius state-level abstract functional interface for ZDDs, Proceedings of the 2nd international conference on Performance evaluation methodologies and tools, October 22-27, 2007, Nantes, France
	Abusaleh Jabir , Dhiraj Pradhan , T. L. Rajaprabhu , A. K. Singh, A Technique for Representing Multiple Output Binary Functions with Applications to Verification and Simulation, IEEE Transactions on Computers, v.56 n.8, p.1133-1145, August 2007
	Paolo Bonzini , Laura Pozzi, Recurrence-aware instruction set selection for extensible embedded processors, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.16 n.10, p.1259-1267, October 2008
	Ion Constantinescu , Walter Binder , Boi Faltings, Selection and ranking of propositional formulas for large-scale service directories, Proceedings of the 20th national conference on Artificial intelligence, p.1406-1411, July 09-13, 2005, Pittsburgh, Pennsylvania
	Shin-Ichi Minato , Ken Satoh , Taisuke Sato, Compiling Bayesian networks by symbolic probability calculation based on zero-suppressed BDDs, Proceedings of the 20th international joint conference on Artifical intelligence, p.2550-2555, January 06-12, 2007, Hyderabad, India
	Laurent Simon, Efficient consequence finding, Proceedings of the 17th international joint conference on Artificial intelligence, p.359-365, August 04-10, 2001, Seattle, WA, USA