Theoret. Informatics Appl. 36, 229-247 (2002)
DOI: 10.1051/ita:2002011

Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs

Henrik Brosenne, Matthias Homeister and Stephan Waack

Institut für Numerische und Angewandte Mathematik, Georg-August-Universität Göttingen, Lotzestr. 16-18, 37083 Göttingen, Germany; homeiste@math.uni-goettingen.de. waack@math.uni-goettingen.de.

(Received November, 2001. Accepted September, 2002.)

Abstract
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

What is OpenURL?