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:
“She thinks of the 4 a.m. lonelinesses that have folded
her up like death, discordant, without logical and
beautiful conclusion. Her teeth break off at the edges.
She would speak.”
—Joy Harjo (b. 1951)
“A sociosphere of contact, control, persuasion and dissuasion, of exhibitions of inhibitions in massive or homeopathic doses...: this is obscenity. All structures turned inside out and exhibited, all operations rendered visible. In America this goes all the way from the bewildering network of aerial telephone and electric wires ... to the concrete multiplication of all the bodily functions in the home, the litany of ingredients on the tiniest can of food, the exhibition of income or IQ.”
—Jean Baudrillard (b. 1929)