Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
Institut für Numerische und Angewandte Mathematik,
Lotzestr. 16-18, 37083 Göttingen, Germany; firstname.lastname@example.org.
Accepted: September 2002
We investigate well-structured graph-driven parity-FBDDs, which strictly generalize the two well-known models parity OBDDs and well-structured graph-driven FBDDs. The first main result is a characterization of the complexity of Boolean functions represented by well-structured graph-driven parity-FBDDs in terms of invariants of the function represented and the graph-ordering used. As a consequence, we derive a lower bound criterion and prove an exponential lower bound for certain linear code functions. The second main result of this paper is a polynomial time algorithm that minimizes the number of nodes in a graph-driven parity-FBDD.
Mathematics Subject Classification: 68Q10 / 68Q60 / 68P05
Key words: Well-structured graph-driven parity-FBDDs / lower bounds / minimization algorithm / complexity theory / data structures for Boolean functions.
© EDP Sciences, 2002