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 : 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},
     mrnumber = {1958241},
     zbl = {1032.68081},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2002011/}
}
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
SP  - 229
EP  - 247
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2002011/
DO  - 10.1051/ita:2002011
LA  - en
ID  - ITA_2002__36_3_229_0
ER  - 
%0 Journal Article
%A Brosenne, Henrik
%A Homeister, Matthias
%A Waack, Stephan
%T Characterizing the complexity of boolean functions represented by well-structured graph-driven parity-FBDDs
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 229-247
%V 36
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2002011/
%R 10.1051/ita:2002011
%G en
%F 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/articles/10.1051/ita:2002011/

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

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

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

[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

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

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

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

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

[12] E.J. Macwilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977). | Zbl

[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

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

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

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

Cité par Sources :