An ordered binary decision diagram is a binary decision diagram using one fixed variable ordering of a binary decision diagram along every root-to-terminal branch. Tests may be omitted, but no branch may test a later variable before an earlier one. For the order , a branch testing is permitted; a branch testing is not. Sharing equal residual Boolean functions can compress the diagram. Applying the reduction rules gives a reduced ordered binary decision diagram, canonical for the chosen order; a different order can have a dramatically different size.
An ordered binary decision diagram with shared equal terminal nodes, no decision node having identical zero and one children, and no two decision nodes having the same tested Boolean variable and the same ordered pair of children. For a fixed variable ordering of a binary decision diagram, it is unique up to labelled graph isomorphism: each nonconstant remaining Boolean cofactor has a uniquely determined first essential Boolean variable, and its two children are recursively determined by its zero and one Boolean cofactors. This uniqueness does not compare different orderings.
A fixed order in which Boolean variables may be tested along each branch of an ordered binary decision diagram. Branches may skip a test, but cannot reverse the order. The order can change the number of distinct remaining Boolean cofactors and therefore the size of the representation.
Articles by others on the same topic
There are currently no matching articles.