The Resource Branching programs and binary decision diagrams : theory and applications, Ingo Wegener, (electronic resource)

Branching programs and binary decision diagrams : theory and applications, Ingo Wegener, (electronic resource)

Label
Branching programs and binary decision diagrams : theory and applications
Title
Branching programs and binary decision diagrams
Title remainder
theory and applications
Statement of responsibility
Ingo Wegener
Creator
Contributor
Provider
Subject
Language
eng
Summary
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
Member of
Cataloging source
CaBNvSL
http://library.link/vocab/creatorName
Wegener, Ingo
Index
index present
LC call number
QA274.76
LC item number
.W44 2000eb
Literary form
non fiction
Nature of contents
  • dictionaries
  • bibliography
http://library.link/vocab/relatedWorkOrContributorName
  • Society for Industrial and Applied Mathematics
  • Society for Industrial and Applied Mathematics
Series statement
SIAM monographs on discrete mathematics and applications
Series volume
4
http://library.link/vocab/subjectName
  • Branching processes
  • Decision making
  • Computational complexity
Target audience
adult
Label
Branching programs and binary decision diagrams : theory and applications, Ingo Wegener, (electronic resource)
Instantiates
Publication
Bibliography note
Includes bibliographical references (p. 379-402) and index
Color
black and white
Contents
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
Dimensions
unknown
Extent
1 electronic text (x, 408 p.)
File format
multiple file formats
Form of item
online
Isbn
9780898719789
Other physical details
ill., digital file.
Reformatting quality
access
Specific material designation
remote
System control number
  • (CaBNvSL)gtp00545523
  • (SIAM)9780898719789
Label
Branching programs and binary decision diagrams : theory and applications, Ingo Wegener, (electronic resource)
Publication
Bibliography note
Includes bibliographical references (p. 379-402) and index
Color
black and white
Contents
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
Dimensions
unknown
Extent
1 electronic text (x, 408 p.)
File format
multiple file formats
Form of item
online
Isbn
9780898719789
Other physical details
ill., digital file.
Reformatting quality
access
Specific material designation
remote
System control number
  • (CaBNvSL)gtp00545523
  • (SIAM)9780898719789

Library Locations

  • African Studies LibraryBorrow it
    771 Commonwealth Avenue, 6th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Alumni Medical LibraryBorrow it
    72 East Concord Street, Boston, MA, 02118, US
    42.336388 -71.072393
  • Astronomy LibraryBorrow it
    725 Commonwealth Avenue, 6th Floor, Boston, MA, 02445, US
    42.350259 -71.105717
  • Fineman and Pappas Law LibrariesBorrow it
    765 Commonwealth Avenue, Boston, MA, 02215, US
    42.350979 -71.107023
  • Frederick S. Pardee Management LibraryBorrow it
    595 Commonwealth Avenue, Boston, MA, 02215, US
    42.349626 -71.099547
  • Howard Gotlieb Archival Research CenterBorrow it
    771 Commonwealth Avenue, 5th Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Mugar Memorial LibraryBorrow it
    771 Commonwealth Avenue, Boston, MA, 02215, US
    42.350723 -71.108227
  • Music LibraryBorrow it
    771 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350723 -71.108227
  • Pikering Educational Resources LibraryBorrow it
    2 Silber Way, Boston, MA, 02215, US
    42.349804 -71.101425
  • School of Theology LibraryBorrow it
    745 Commonwealth Avenue, 2nd Floor, Boston, MA, 02215, US
    42.350494 -71.107235
  • Science & Engineering LibraryBorrow it
    38 Cummington Mall, Boston, MA, 02215, US
    42.348472 -71.102257
  • Stone Science LibraryBorrow it
    675 Commonwealth Avenue, Boston, MA, 02445, US
    42.350103 -71.103784
Processing Feedback ...