Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
Henrik Brosenne, Matthias Homeister, Stephan Waack (2002)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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...