Cover Image

Applications of zero-suppressed decision diagrams /

Bibliographic Details
Main Authors: Sasao, Tsutomu, 1950- (Author), Butler, Jon T. (Author)
Format: eBook
Language:English
Published: San Rafael, California (1537 Fourth Street, San Rafael, CA 94901 USA) : Morgan & Claypool, 2015.
Series:Synthesis lectures on digital circuits and systems ; # 45.
Subjects:
Decision logic tables > Mathematics.
Graphic methods.
State-space methods.
CUDD package
binary decision diagram
data-structure
frontier-based method
graph enumeration
intrusion detection
logic function
non-deterministic automata
one-hot code
prime implicant
regular expression matching
sum-of-products expression
zero-suppressed decision diagram
Electronic books.
Online Access:Connect to the full text of this electronic book
Table of Contents:
  • 1. Introduction to zero-suppressed decision diagrams / Alan Mishchenko
  • Chapter summary
  • 1.1 Introduction
  • 1.2 Definitions
  • 1.2.1 BDD and ZDD reduction rules
  • 1.3 Comparing BDDs and ZDDs
  • 1.3.1 Boolean functions
  • 1.3.2 Sets of subsets
  • 1.3.3 Cube covers
  • 1.4 Basic ZDD procedures
  • 1.4.1 Procedures working with functions
  • 1.4.2 Procedures working with covers
  • 1.4.3 Generic structure of a recursive ZDD procedure
  • 1.5 Manipulation of sets
  • 1.5.1 A case study of the CUDD source code
  • 1.6 Manipulation of cube covers
  • 1.7 Mixed ZDD/BDD applications
  • 1.7.1 Computation of the set of all primes
  • 1.7.2 Computation of an irredundant SOP
  • 1.8 A list of published ZDD applications
  • 1.9 Conclusions
  • 1.10 Acknowledgements
  • 1.11 Appendix A
  • 1.12 Appendix B
  • 1.13 Exercises
  • References
  • 2. Efficient generation of prime implicants and irredundant sum-of-products expressions / Tsutomu Sasao
  • Chapter summary
  • 2.1 Logical expressions
  • 2.2 Monotone and unate functions
  • 2.3 Prime implicants
  • 2.4 Generation of all the prime implicants
  • 2.5 Generation of irredundant sum-of-products expressions
  • 2.6 Morreale's algorithm
  • 2.7 Conclusion and comments
  • 2.8 Exercises
  • References
  • 3. The power of enumeration-BDD/ZDD-based algorithms for tackling combinatorial explosion / Shin-ichi Minato
  • Chapter summary
  • 3.1 Introduction
  • 3.2 BDDs/ZDDs and graph enumeration
  • 3.3 Frontier-based method
  • 3.3.1 Knuth's SimPath algorithm
  • 3.3.2 Frontier-based method for various problems
  • 3.3.3 Recent topics on the path enumeration problem
  • 3.4 Conclusion
  • 3.5 Exercises
  • References
  • 4. Regular expression matching using zero-suppressed decision diagrams / Shinobu Nagayama
  • Chapter summary
  • 4.1 Introduction
  • 4.2 Preliminaries
  • 4.2.1 Regular expressions and finite automaton
  • 4.2.2 Binary decision diagrams
  • 4.3 BDDs and ZDDs for NFAs
  • 4.3.1 Representations of NFAs using BDDs
  • 4.3.2 Representations of NFAs using ZDDs
  • 4.4 Matching method using BDDs and ZDDs
  • 4.4.1 Regular expression matching method using BDDs [39]
  • 4.4.2 Regular expression matching method using ZDDs
  • 4.5 Experimental results
  • 4.5.1 Comparison of the number of nodes
  • 4.5.2 Comparison of computation time
  • 4.6 Conclusion and comments
  • AcknowledgmentS
  • 4.7 Exercises
  • References
  • A. Solutions
  • Authors' and editors' biographies
  • Index.