Descripción del título
Branching programs and bina...
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
Monografía
monografia Rebiun36988085 https://catalogo.rebiun.org/rebiun/record/Rebiun36988085 m eo d cr bn |||m|||a 110109s2000 paua ob 001 0 eng d 00035749 0-89871-978-X 10.1137/1.9780898719789 doi DT04 SIAM CUNEF 991000509033208131 CaBNVSL. CaBNVSL. CaBNVSL eng 519.2/34 21 Wegener, Ingo Branching programs and binary decision diagrams theory and applications Ingo Wegener Philadelphia, Pa. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104) 2000 Philadelphia, Pa. Philadelphia, Pa. Society for Industrial and Applied Mathematics (SIAM, 3600 Market Street, Floor 6, Philadelphia, PA 19104) 1 electronic text (x, 408 p.) ill., digital file 1 electronic text (x, 408 p.) Text txt computer c online resource cr SIAM monographs on discrete mathematics and applications 4 Bibliographic Level Mode of Issuance: Monograph Includes bibliographical references (p. 379-402) and index Preface -- Introduction -- 1. Introduction -- 2. BPs and decision trees (DTs) -- 3. Ordered binary decision diagrams (OBDDs) -- 4. The OBDD size of selected functions -- 5. The variable-ordering problem -- 6. Free BDDs (FBDDs) and read-once BPs -- 7. BDDs with repeated tests -- 8. Decision diagrams (DDs) based on other decomposition rules -- 9. Integer-valued DDs -- 10. Nondeterministic DDs -- 11. Randomized BDDs and algorithms -- 12. Summary of the theoretical results -- 13. Applications in verification and model checking -- 14. Further CAD applications -- 15. Application in optimization, counting, and genetic programming -- Bibliography -- Index 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 Also available in print version Mode of access: World Wide Web System requirements: Adobe Acrobat Reader English Branching processes Decision making- Mathematical models Computational complexity Society for Industrial and Applied Mathematics 0-89871-458-3 SIAM monographs on discrete mathematics and applications 4