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

Henrik Brosenne; Matthias Homeister; Stephan Waack

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 36, Issue: 3, page 229-247
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBrosenne, Henrik, Homeister, Matthias, and Waack, Stephan. "Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs." RAIRO - Theoretical Informatics and Applications 36.3 (2010): 229-247. <http://eudml.org/doc/92699>.

@article{Brosenne2010,

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.
},

author = {Brosenne, Henrik, Homeister, Matthias, Waack, Stephan},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Well-structured graph-driven parity-FBDDs; lower bounds;
minimization algorithm; complexity theory; data structures for Boolean functions.; polynomial time algorithm},

language = {eng},

month = {3},

number = {3},

pages = {229-247},

publisher = {EDP Sciences},

title = {Characterizing the Complexity of Boolean Functions represented by Well-Structured Graph-Driven Parity-FBDDs},

url = {http://eudml.org/doc/92699},

volume = {36},

year = {2010},

}

TY - JOUR

AU - Brosenne, Henrik

AU - Homeister, Matthias

AU - Waack, Stephan

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

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 36

IS - 3

SP - 229

EP - 247

AB -
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.

LA - eng

KW - Well-structured graph-driven parity-FBDDs; lower bounds;
minimization algorithm; complexity theory; data structures for Boolean functions.; polynomial time algorithm

UR - http://eudml.org/doc/92699

ER -

## References

top- B. Bollig, St. Waack and P. Woelfel, Parity graph-driven read-once branching programs and an exponential lower bound for integer multiplication, in Proc. 2nd IFIP International Conference on Theoretical Computer Science (2002). Zbl1100.68024
- Y. Breitbart, H.B. Hunt and D. Rosenkrantz, The size of binary decision diagrams representing Boolean functions. Theoret. Comput. Sci.145 (1995) 45-69. Zbl0874.68283
- H. Brosenne, M. Homeister and St. Waack, Graph-driven free parity BDDs: Algorithms and lower bounds, in Proc. 26th MFCS. Springer Verlag, Lecture Notes in Comput. Sci.2136 (2001) 212-223. Zbl0999.68068
- R. Bryant, On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput.40 (1991) 205-213. Zbl1220.68060
- R.E. Bryant, Symbolic manipulation of Boolean functions using a graphical representation, in Proc. 22nd DAC. Piscataway, NJ (1985) 688-694.
- R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput.35 (1986) 677-691. Zbl0593.94022
- D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput.9 (1990) 251-280. Zbl0702.65046
- J. Gergov and Ch. Meinel, Frontiers of feasible and probabilistic feasible Boolean manipulation with branching programs, in Proc. 10th STACS. Springer Verlag, Lecture Notes in Comput. Sci.665 (1993) 576-585. Zbl0798.68078
- J. Gergov and Ch. Meinel, Mod-2-OBDDs - A data structure that generalizes exor-sum-of-products and ordered binary decision diagrams. Formal Methods in System Design8 (1996) 273-282.
- S. Jukna, Entropy of contact circuits and lower bounds on their complexit. Theoret. Comput. Sci.57 (1988) 113-129. Zbl0655.94020
- S. Jukna, Linear codes are hard for oblivious read-once parity branching programs. Inform. Process. Lett.69 (1999) 267-269. Zbl1002.68054
- E.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977). Zbl0369.94008
- D. Sieling, Lower bounds for linear transformed OBDDs and FBDDs, in Proc. 19th FSTTCS. Springer Verlag, Lecture Notes in Comput. Sci.1738 (1999) 356-368. Zbl0958.68071
- D. Sieling and I. Wegener, Graph driven BDDs - A new data structure for Boolean functions. Theoret. Comput. Sci.141 (1995) 238-310. Zbl0873.68036
- St. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams. Inform. Comput.166 (2001) 61-70. Zbl1003.68049
- I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (2000).