# 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 - Informatique Théorique et Applications (2002)

- 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 - Informatique Théorique et Applications 36.3 (2002): 229-247. <http://eudml.org/doc/245172>.

@article{Brosenne2002,

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 - Informatique Théorique et Applications},

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

language = {eng},

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/245172},

volume = {36},

year = {2002},

}

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 - Informatique Théorique et Applications

PY - 2002

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/245172

ER -

## References

top- [1] 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
- [2] 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.68283MR1339474
- [3] 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.68068MR1907013
- [4] R. Bryant, On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput. 40 (1991) 205-213. Zbl1220.68060MR1094031
- [5] R.E. Bryant, Symbolic manipulation of Boolean functions using a graphical representation, in Proc. 22nd DAC. Piscataway, NJ (1985) 688-694.
- [6] R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
- [7] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9 (1990) 251-280. Zbl0702.65046MR1056627
- [8] 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.68078MR1244146
- [9] 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 Design 8 (1996) 273-282.
- [10] S. Jukna, Entropy of contact circuits and lower bounds on their complexit. Theoret. Comput. Sci. 57 (1988) 113-129. Zbl0655.94020MR961268
- [11] S. Jukna, Linear codes are hard for oblivious read-once parity branching programs. Inform. Process. Lett. 69 (1999) 267-269. Zbl1002.68054MR1692496
- [12] E.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977). Zbl0369.94008
- [13] 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
- [14] D. Sieling and I. Wegener, Graph driven BDDs – A new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 238-310. Zbl0873.68036
- [15] St. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams. Inform. Comput. 166 (2001) 61-70. Zbl1003.68049MR1823703
- [16] I. Wegener, Branching Programs and Binary Decision Diagrams – Theory and Applications. SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (2000). Zbl0956.68068

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.