search for books and compare prices
Tables of Contents for Branching Programs and Binary Decision Diagrams
Chapter/Section Title
Page #
Page Count
Preface
ix
Introduction
1
18
Branching Programs (BPs) and Binary Decision Diagrams (BDDs)
1
4
Motivations from Theory
5
1
Motivations from Applications
6
5
On the Inherent Complexity of Some Problems
11
3
Survey
14
3
Exercises
17
2
BPs and Decision Trees (DTs)
19
26
BPs, Circuits, Formulas, and Space
19
7
Lower Bound Techniques for BPs
26
4
Upper Bound Techniques for BPs
30
5
Algorithms on BPs
35
2
DTs
37
6
Exercises and Open Problems
43
2
Ordered Binary Decision Diagrams (OBDDs)
45
24
OBDDs
45
4
OBDDs and Deterministic Finite Automata (DFAs)
49
2
Efficient Algorithms on OBDDs
51
6
Breadth-First Manipulation of OBDDs
57
3
Parallel Computers and OBDDs
60
1
Incompletely Specified Boolean Functions
61
5
Exercises and Open Problems
66
3
The OBDD Size of Selected Functions
69
24
OBDDs and Communication Complexity
69
2
Read-Once Projections
71
3
Storage Access
74
1
Addition
75
2
Multiplication
77
3
Squaring and Division
80
1
Symmetric Functions
81
1
General Threshold Functions
82
2
Functions with Short Disjunctive Normal Forms (DNFs)
84
1
The Hidden Weighted Bit Function
84
3
Read-Once Formulas
87
1
Selected Functions on Matrices
88
2
Exercises and Open Problems
90
3
The Variable-Ordering Problem
93
36
The Variable-Ordering Problem
93
1
Random Functions
94
2
Nice, Ugly, and Ambiguous Functions
96
3
The Complexity of the Variable-Ordering Problem
99
1
The Computation of Optimal Variable Orderings
100
5
Heuristics for the Computation of Good Variable Orderings
105
2
Changing the Variable Ordering
107
9
Reordering Techniques
116
5
Transformations of Boolean Functions
121
4
Exercises and Open Problems
125
4
Free BDDs (FBDDs) and Read-Once BPs
129
32
Definition and Upper Bound Techniques
129
4
Lower Bound Techniques
133
10
Algorithms on FBDDs
143
3
Algorithms on G-FBDDs
146
9
Search Problems
155
3
Exercises and Open Problems
158
3
BDDs with Repeated Tests
161
34
The Landscape between OBDDs and BPs
161
2
Upper Bound Techniques
163
5
Efficient Algorithms and NP-Hardness Results
168
6
Lower Bound Techniques for (1, +k)-BPs
174
3
Lower Bound Techniques for Oblivious BDDs
177
11
Lower Bound Techniques for k-BPs
188
4
Lower Bounds for Depth-Restricted BPs
192
1
Exercises and Open Problems
193
2
Decision Diagrams (DDs) Based on Other Decomposition Rules
195
20
Zero-Suppressed Binary Decision Diagrams (ZBDDs)
195
7
Ordered Functional Decision Diagrams (OFDDs)
202
9
Ordered Kronecker Functional Decision Diagrams (OKFDDs)
211
1
Exercises and Open Problems
212
3
Integer-Valued DDs
215
22
Multivalued Decision Diagrams (MDDs)
215
1
Multiterminal BDDs (MTBDDs)
216
4
Binary Moment Diagrams (BMDs)
220
5
Hybrid Decision Diagrams (HDDs)
225
1
Edge-Valued Binary Decision Diagrams (EVBDDs)
225
5
Edge-Valued Binary Moment Diagrams (*BMDs)
230
5
Exercises
235
2
Nondeterministic DDs
237
34
Different Modes and Models of Nondeterminism
237
4
Upper Bound Techniques
241
4
Lower Bound Techniques
245
6
Partitioned OBDDs
251
10
Algorithms for EXOR-OBDDs
261
7
Exercises and Open Problems
268
3
Randomized BDDs and Algorthms
271
32
Randomized Equivalence Tests
271
3
Randomized BDD Variants
274
2
Probability Amplification
276
4
Throw the Coins First
280
1
Upper Bound Results
281
6
Efficient Algorithms and Hardness Results
287
2
Lower Bounds for Randomized OBDDs and k-OBDDs
289
4
Lower Bounds for Randomized FBDDs and k-BPs
293
6
Exercises and Open Problems
299
4
Summary of the Theoretical Results
303
10
Algorithmic Properties
303
2
Bounds for Selected Functions
305
4
Complexity Landscapes
309
4
Applications in Verification and Model Checking
313
18
Verification of Combinational Circuits
313
8
Verification of Sequential Circuits
321
5
Symbolic Model Checking
326
5
Further CAD Applications
331
26
Two-Level Logic Minimization
331
8
Multilevel Logic Synthesis
339
4
Functional Simulation
343
2
Test Generation
345
1
Timing Analysis
346
3
Technology Mapping
349
3
Synchronizing Sequences
352
1
Boolean Unification
353
4
Application in Optimization, Counting, and Genetic Programming
357
22
Integer Programming
357
4
Network Flow
361
5
Counting Problems
366
4
Genetic Programming
370
9
Bibliography
379
24
Index
403