Applications of Zero-suppressed Decision Diagrams
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 Morrealefs 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 Knuthfs 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
Authorsf and Editorsf Biographies . . . . . . . .  . . . 99

Back