Branching Programs and Binary Decision Diagrams: Theory and ApplicationsSIAM, 01.01.2000 - 418 Seiten 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. |
Inhalt
DT04_ch1 | 1 |
DT04_ch2 | 19 |
DT04_ch3 | 45 |
DT04_ch4 | 69 |
DT04_ch5 | 93 |
DT04_ch6 | 129 |
DT04_ch7 | 161 |
DT04_ch8 | 195 |
DT04_ch10 | 237 |
DT04_ch11 | 271 |
DT04_ch12 | 303 |
DT04_ch13 | 313 |
DT04_ch14 | 331 |
DT04_ch15 | 357 |
DT04_bm | 379 |
DT04_ch9 | 215 |
Andere Ausgaben - Alle anzeigen
Branching Programs and Binary Decision Diagrams: Theory and Applications Ingo Wegener Eingeschränkte Leseprobe - 2000 |
Branching Programs and Binary Decision Diagrams: Theory and Applications Ingo Wegener Keine Leseprobe verfügbar - 2000 |
Häufige Begriffe und Wortgruppen
addition algorithm apply approach assignments BDDs binary Boolean functions called Chapter choose chosen circuit column communication complexity computation consider consists constant construction contains corresponding decision defined Definition depend described Design discuss easy edges efficient elimination equals equivalence error essentially example exists exponential FBDDs fixed formula function f given graph Hence holds implies input label layer leads least leaving Lemma length linear lower bound matrix methods minimal Moreover multiplication nodes OBDD obtain operations optimal output path performed polynomial polynomial-size position possible present probability problem Proof prove randomized reachable reached reduced replaced representation represented respect restricted result rule satisfiability simple sink starting step subfunctions sufficient synthesis techniques Theorem tion transformation variable ordering verification vertices Wegener weight xi-node