OBDDs
E824078
binary decision diagram
canonical representation of Boolean functions
graph-based data structure
reduced ordered binary decision diagram
symbolic representation
OBDDs (Ordered Binary Decision Diagrams) are a canonical, graph-based representation of Boolean functions that enables efficient manipulation and verification in formal methods and model checking.
Observed surface forms (2)
Statements (52)
| Predicate | Object |
|---|---|
| instanceOf |
binary decision diagram
ⓘ
canonical representation of Boolean functions ⓘ graph-based data structure ⓘ reduced ordered binary decision diagram ⓘ symbolic representation ⓘ |
| abbreviation | OBDD NERFINISHED ⓘ |
| canonicalUnderCondition |
fixed variable ordering
ⓘ
reduction rules applied ⓘ |
| constraint | variables follow a total order along all paths ⓘ |
| definedBy | Bryant 1986 paper on graph-based algorithms for Boolean function manipulation ⓘ |
| edgeType |
high (true) edge
ⓘ
low (false) edge ⓘ |
| fullName | Ordered Binary Decision Diagram NERFINISHED ⓘ |
| generalizationOf | binary decision tree ⓘ |
| hasComponent |
decision nodes
ⓘ
directed edges ⓘ root node ⓘ terminal nodes ⓘ |
| hasProperty |
can be exponentially larger than other representations for some functions
ⓘ
can be exponentially more compact than truth tables for some functions ⓘ each variable is tested at most once along any path ⓘ no isomorphic subgraphs ⓘ no redundant tests ⓘ reduced form is canonical for a fixed variable ordering ⓘ size strongly depends on variable ordering ⓘ supports efficient equivalence checking of Boolean functions ⓘ supports efficient logical operations ⓘ supports efficient model counting for Boolean functions ⓘ supports efficient quantification over variables ⓘ supports efficient restriction of variables ⓘ supports efficient satisfiability checking ⓘ variables are tested in a fixed order ⓘ |
| hasVariant | ROBDD NERFINISHED ⓘ |
| implementedIn |
BuDDy library
NERFINISHED
ⓘ
CUDD library NERFINISHED ⓘ JavaBDD library NERFINISHED ⓘ |
| introducedBy | Randal E. Bryant NERFINISHED ⓘ |
| represents | Boolean function ⓘ |
| terminalNodeValues |
0
ⓘ
1 ⓘ |
| usedIn |
combinational circuit verification
ⓘ
equivalence checking of circuits ⓘ formal verification ⓘ hardware verification ⓘ logic synthesis ⓘ model checking ⓘ probabilistic model analysis ⓘ software verification ⓘ symbolic model checking ⓘ test pattern generation ⓘ timing analysis ⓘ |
| yearIntroduced | 1986 ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.