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

Abstract

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

How to cite

top

Brosenne, 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. [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. [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. [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. [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. [5] R.E. Bryant, Symbolic manipulation of Boolean functions using a graphical representation, in Proc. 22nd DAC. Piscataway, NJ (1985) 688-694. 
  6. [6] R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
  7. [7] D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput. 9 (1990) 251-280. Zbl0702.65046MR1056627
  8. [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. [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. [10] S. Jukna, Entropy of contact circuits and lower bounds on their complexit. Theoret. Comput. Sci. 57 (1988) 113-129. Zbl0655.94020MR961268
  11. [11] S. Jukna, Linear codes are hard for oblivious read-once parity branching programs. Inform. Process. Lett. 69 (1999) 267-269. Zbl1002.68054MR1692496
  12. [12] E.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977). Zbl0369.94008
  13. [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. [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. [15] St. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams. Inform. Comput. 166 (2001) 61-70. Zbl1003.68049MR1823703
  16. [16] I. Wegener, Branching Programs and Binary Decision Diagrams – Theory and Applications. SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (2000). Zbl0956.68068

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.