Branching Programs and Binary Decision Diagrams: Theory and Applications

✍ Scribed by Ingo Wegener

• Publisher: Society for Industrial Mathematics
• Year: 1987
• Tongue: English
• Leaves: 419
• Series: Monographs on Discrete Mathematics and Applications
• Category: Library

✦ Synopsis

Finite functions (in particular, Boolean functions) play a fundamental role in computer science and discrete mathematics. This book describes representations of Boolean functions that have small size for many important functions and which allow efficient work with the represented functions. The representation size of important and selected functions is estimated, upper and lower bound techniques are studied, efficient algorithms for operations on these representations are presented, and the limits of those techniques are considered.

This book is the first comprehensive description of theory and applications. Research areas like complexity theory, efficient algorithms, data structures, and discrete mathematics will benefit from the theory described in this book. The results described within have applications in verification, computer-aided design, model checking, and discrete mathematics. This is the only book to investigate the representation size of Boolean functions and efficient algorithms on these representations.

✦ Table of Contents

Branching Programs and Binary Decision Diagrams......Page 2
SIAM Monographs on Discrete Mathematics and Applications......Page 3
ISBN 0-89871-458-3......Page 5
Contents......Page 6
Preface......Page 10
1 Introduction......Page 12
2 BPs and Decision Trees (DTs)......Page 30
3 Ordered Binary Decision Diagrams (OBDDs)......Page 56
4 The OBDD Size of Selected Functions......Page 80
5 The Variable-Ordering Problem......Page 104
6 Free BDDs (FBDDs) and Read-Once BPs......Page 140
7 BDDs with Repeated Tests......Page 172
8 Decision Diagrams (DDs) Based on Other Decomposition Rules......Page 206
9 Integer-Valued DDs......Page 226
10 Nondeterministic DDs......Page 248
11 Randomized BDDs and Algorithms......Page 282
12 Summary of the Theoretical Results......Page 314
13 Applications in Verification and Model Checking......Page 324
14 Further CAD Applications......Page 342
15 Applications in Optimization, Counting, and Genetic Programming......Page 368
Bibliography......Page 390
Index......Page 414