= Ordered binary decision diagram
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 $x<y<z$, a branch testing $x,z$ is permitted; a branch testing $z,x$ 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.
Back to article page