no. 3

Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 229-247.

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.

DOI : https://doi.org/10.1051/ita:2002011
Classification : 68Q10,  68Q60,  68P05
Mots clés : well-structured graph-driven parity-FBDDs, lower bounds, minimization algorithm, complexity theory, data structures for boolean functions 
@article{ITA_2002__36_3_229_0,
     author = {Brosenne, Henrik and Homeister, Matthias and Waack, Stephan},
     title = {Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {229--247},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ita:2002011},
     zbl = {1032.68081},
     mrnumber = {1958241},
     language = {en},
     url = {http://www.numdam.org/item/ITA_2002__36_3_229_0/}
}
Brosenne, Henrik; Homeister, Matthias; 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, Tome 36 (2002) no. 3, pp. 229-247. doi : 10.1051/ita:2002011. http://www.numdam.org/item/ITA_2002__36_3_229_0/

[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).

[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. | MR 1339474 | Zbl 0874.68283

[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. | MR 1907013 | Zbl 0999.68068

[4] R. Bryant, On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput. 40 (1991) 205-213. | MR 1094031 | Zbl 1220.68060

[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. | Zbl 0593.94022

[7] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9 (1990) 251-280. | MR 1056627 | Zbl 0702.65046

[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. | MR 1244146 | Zbl 0798.68078

[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. | MR 961268 | Zbl 0655.94020

[11] S. Jukna, Linear codes are hard for oblivious read-once parity branching programs. Inform. Process. Lett. 69 (1999) 267-269. | MR 1692496 | Zbl 1002.68054

[12] E.J. Macwilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977). | Zbl 0369.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. | Zbl 0958.68071

[14] D. Sieling and I. Wegener, Graph driven BDDs - A new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 238-310. | Zbl 0873.68036

[15] St. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams. Inform. Comput. 166 (2001) 61-70. | MR 1823703 | Zbl 1003.68049

[16] I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (2000). | Zbl 0956.68068