Logical Operations On BDDs
Many logical operations on BDDs can be implemented by polynomial-time graph manipulation algorithms.
- conjunction
- disjunction
- negation
- existential abstraction
- universal abstraction
However, repeating these operations several times, for example forming the conjunction or disjunction of a set of BDDs, may in the worst case result in an exponentially big BDD. This is because any of the preceding operations for two BDDs may result in a BDD with a size proportional to the product of the BDDs' sizes, and consequently for several BDDs the size may be exponential.
Read more about this topic: Binary Decision Diagram
Famous quotes containing the words logical and/or operations:
“It is merely a linguistic peculiarity, not a logical fact, that we say “that is red” instead of “that reddens,” either in the sense of growing, becoming, red, or in the sense of making something else red.”
—John Dewey (1859–1952)
“You can’t have operations without screams. Pain and the knife—they’re inseparable.”
—Jean Scott Rogers. Robert Day. Mr. Blount (Frank Pettingell)