| Issue |
RAIRO-Theor. Inf. Appl.
Volume 36, Number 3, July/September 2002
|
|
|---|---|---|
| Page(s) | 229 - 247 | |
| DOI | https://doi.org/10.1051/ita:2002011 | |
| Published online | 15 December 2002 | |
Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs
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
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.