Tsutomu Sasao and Jon T. Butler (e.d.)
Morgan & Claypool Publishers,
Dec. 2014.
Preface . . . . . . . . . . . . . . . . . . . . . . . . xv Acknowledgments. . . . . . . . . . . . . . . . . . . . xvii 1 Introduction to Zero-Suppressed Decision Diagrams . . . 1 Alan Mishchenko Chapter Summary . . . . . . . . . . . . . . . . . . . . . 1 1.1 Introduction. . . . . . . . . . . . . . . . . . . . . 1 1.2 Definitions . . . . . . . . . . . . . . . . . . . . . 3 1.2.1 BDD and ZDD Reduction Rules . . . . . . . . . . . . 5 1.3 Comparing BDDs and ZDDs . . . . . . . . . . . . . . . 7 1.3.1 Boolean Functions . . . . . . . . . . . . . . . . . 7 1.3.2 Sets of Subsets . . . . . . . . . . . . . . . . . . 7 1.3.3 Cube Covers . . . . . . . . . . . . . . . . . . . . 9 1.4 Basic ZDD Procedures. . . . . . . . . . . . . . . . . 11 1.4.1 Procedures Working with Functions . . . . . . . . . 11 1.4.2 Procedures Working with Covers . . . . . . . . . . 11 1.4.3 Generic Structure of a Recursive ZDD Procedure . . 13 1.5 Manipulation of Sets . . . . . . . . . . . . . . . . 14 1.5.1 A Case Study of the CUDD Source Code .. . . . . . . 15 1.6 Manipulation of Cube Covers . . . . . . . . . . . . . 18 1.7 Mixed ZDD/BDD Applications . . . . . . .. . . . . . . 19 1.7.1 Computation of the Set of All Primes .. . . . . . . 19 1.7.2 Computation of an Irredundant SOP . . . . . . . . . 20 1.8 A List of Published ZDD Applications . . . . . . . . 22 1.9 Conclusions . . . . . . . . . . . . . . . . . . . . . 23 1.10 Acknowledgements . . . . . . . . . . . . . . . . . . 23 1.11 Appendix A . . . . . . . . . . . . . . . . . . . . . 23 1.12 Appendix B. . . .. . . . . . . . . . . . . . . . . . 25 1.13 Exercises . . . .. . . . . . . . . . . . . . . . . . 29 References . . . . . .. . . . . . . . . . . . . . . . . . 30 2 Efficient Generation of Prime Implicants and Irredundant Sum-of-Products Expressions . . . . . . . . . . . . . . . 35 Tsutomu Sasao Chapter Summary . . . . . . . . . . . . . . . . . . . . . 35 2.1 Logical Expressions . . . . . . . . . . . . . . . . . 35 2.2 Monotone and Unate Functions . . . . . . . . . . . . . 35 2.3 Prime Implicants . . . . . . . . . . . . . . . . . . . 37 2.4 Generation of All the Prime Implicants . . . . . . . . 37 2.5 Generation of Irredundant Sum-of-Products Expressions. 41 2.6 Morrealefs Algorithm . . . . . . . . . . . . . . . . 43 2.7 Conclusion and Comments. . . . . . . . . . . . . . . . 46 2.8 Exercises . . . . . . .. . . . . . . . . . . . . . . . 46 References . . . . . . . . . . . . . . . . . . . . . . . . 47 3 The Power of Enumeration?BDD/ZDD-Based Algorithms for Tackling Combinatorial Explosion . . . . . . . . . . . . 49 Shin-ichi Minato Chapter Summary . . . . . . . . . . . . . . . . . . . . . 49 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . 49 3.2 BDDs/ZDDs and Graph Enumeration . . . . . . . . . . . 51 3.3 Frontier-Based Method . . . . . . . . . . . . . . . . 53 3.3.1 Knuthfs SimPath Algorithm . . . . . . . . . . . . . 53 3.3.2 Frontier-Based Method for Various Problems . . . . . 55 3.3.3 Recent Topics on the Path Enumeration Problem . . . 57 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . 59 3.5 Exercises . . . . . . . . . . . . . . . . . . . . . . 59 References . . . . . . . . . . . . . . . . . . . . . . . . 60 4 Regular Expression Matching Using Zero-Suppressed Decision Diagrams . 63 Shinobu Nagayama Chapter Summary . . . . . . . . . . . . . . . .. . . . . . 63 4.1 Introduction . . . . . . . . . . . . . . . . . . . . . 64 4.2 Preliminaries . . . . . . . . . . . . . . .. . . . . . 66 4.2.1 Regular Expressions and Finite Automaton . . . . . . 66 4.2.2 Binary Decision Diagrams . . . . . . . . . . . . . . 69 4.3 BDDs and ZDDs for NFAs . . . . . . . . . . . . . . . . 70 4.3.1 Representations of NFAs Using BDDs . . . . . . . . . 70 4.3.2 Representations of NFAs Using ZDDs . . . . . . . . . 71 4.4 Matching Method Using BDDs and ZDDs . . . . . . . . . 74 4.4.1 Regular Expression Matching Method Using BDDs . . . 75 4.4.2 Regular Expression Matching Method Using ZDDs . . . 78 4.5 Experimental Results . . . . . . . . . . . . . . . . . 81 4.5.1 Comparison of the Number of Nodes . . . . . . . . . 82 4.5.2 Comparison of Computation Time . . . . . . . . . . . 83 4.6 Conclusion and Comments . . . . . . . . . . . . . . . 83 Acknowledgments. . . . . . . . . . . . . . . . . . . . . . 84 4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . 84 References . . . . . . . . . . . . . . . . . . . . . . . . 85 A Solutions . . . . . . . . . . . . . . . . . . . . . . . 89 A.1 Chapter 1 . . . . . . . . . . . . . . . . . . . . . . 89 A.2 Chapter 2 . . . . . . . . . . . . . . . . . . . . . . 91 A.3 Chapter 3 . . . . . . . . . . . . . . . . . . . . . . 93 A.4 Chapter 4 . . . . . . . . . . . . . . . . . . . . . . 96 Authorsf and Editorsf Biographies . . . . . . . . . . . 99