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

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 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
  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.  
  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.  
  4. R. Bryant, On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput.40 (1991) 205-213.  
  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.  
  7. D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput.9 (1990) 251-280.  
  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.  
  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 Design8 (1996) 273-282.  
  10. S. Jukna, Entropy of contact circuits and lower bounds on their complexit. Theoret. Comput. Sci.57 (1988) 113-129.  
  11. S. Jukna, Linear codes are hard for oblivious read-once parity branching programs. Inform. Process. Lett.69 (1999) 267-269.  
  12. E.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977).  
  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.  
  14. D. Sieling and I. Wegener, Graph driven BDDs - A new data structure for Boolean functions. Theoret. Comput. Sci.141 (1995) 238-310.  
  15. St. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams. Inform. Comput.166 (2001) 61-70.  
  16. I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (2000).  

NotesEmbed ?

top

You must be logged in to post comments.