Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR00-013 | 14th February 2000 00:00

Algebraic and Uniqueness Properties of Parity Ordered Binary Decision Diagrams and their Generalization


Authors: Daniel Král
Publication: 6th March 2000 13:03
Downloads: 1214


Ordered binary decision diagrams (OBDDs) and parity ordered binary
decision diagrams have proved their importance as data structures
representing Boolean functions. In addition to parity OBDDs we study
their generalization which we call parity AOBDDs, give the algebraic
characterization theorem and compare their minimal size to the size
of parity OBDDs.

We prove that the constraint that no arcs test conditions of type
$x_i=0$ does not affect the node--size of parity (A)OBDDs and we give
an efficient algorithm for finding node--minimal parity (A)OBDDs
with this additional constraint. We define so--called uniqueness
conditions, use them to obtain a canonical form for parity OBDDs and
discuss similar results for parity AOBDDs.

Algorithms for minimization and creating the form which satisfies
the uniqueness conditions for parity OBDDs running in time $O(S^3)$ and
for parity AOBDDs running in time $O(nS^3)$ are presented ($n$ is
the number of variables, $S$ is the number of vertices); both
the algorithms are quite simple.

All the results are also extended to case of shared parity OBDDs and
shared parity AOBDDs --- data structures for representation of Boolean
function sequences.

ISSN 1433-8092 | Imprint