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
Access Full Article
top
Abstract
topHow 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 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- 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).
- Y. Breitbart, H.B. Hunt and D. Rosenkrantz, The size of binary decision diagrams representing Boolean functions. Theoret. Comput. Sci.145 (1995) 45-69.
- 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.
- R. Bryant, On the complexity of VLSI implementations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput.40 (1991) 205-213.
- R.E. Bryant, Symbolic manipulation of Boolean functions using a graphical representation, in Proc. 22nd DAC. Piscataway, NJ (1985) 688-694.
- R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput.35 (1986) 677-691.
- D. Coppersmith and S. Winograd, Matrix multiplication via arithmetic progressions. J. Symb. Comput.9 (1990) 251-280.
- 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.
- 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.
- S. Jukna, Entropy of contact circuits and lower bounds on their complexit. Theoret. Comput. Sci.57 (1988) 113-129.
- S. Jukna, Linear codes are hard for oblivious read-once parity branching programs. Inform. Process. Lett.69 (1999) 267-269.
- E.J. MacWilliams and N.J.A. Sloane, The Theory of Error-Correcting Codes. Elsevier (1977).
- 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.
- D. Sieling and I. Wegener, Graph driven BDDs - A new data structure for Boolean functions. Theoret. Comput. Sci.141 (1995) 238-310.
- St. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams. Inform. Comput.166 (2001) 61-70.
- I. Wegener, Branching Programs and Binary Decision Diagrams - Theory and Applications. SIAM, Philadelphia, SIAM Monogr. Discrete Math. Appl. (2000).
NotesEmbed ?
topYou 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.