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:
“The truth is, that common-sense, or thought as it first emerges above the level of the narrowly practical, is deeply imbued with that bad logical quality to which the epithet metaphysical is commonly applied; and nothing can clear it up but a severe course of logic.”
—Charles Sanders Peirce (1839–1914)
“You can’t have operations without screams. Pain and the knife—they’re inseparable.”
—Jean Scott Rogers. Robert Day. Mr. Blount (Frank Pettingell)