# On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

Beate Bollig; Martin Löbbing; Martin Sauerhoff; Ingo Wegener

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 33, Issue: 2, page 103-115
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBollig, Beate, et al. "On the Complexity of the Hidden Weighted Bit Function for Various BDD Models." RAIRO - Theoretical Informatics and Applications 33.2 (2010): 103-115. <http://eudml.org/doc/221977>.

@article{Bollig2010,

abstract = {
Ordered binary decision diagrams (OBDDs) and several more general BDD models
have turned out to be representations of Boolean functions which are useful
in applications like verification, timing analysis, test pattern generation or
combinatorial optimization.
The hidden weighted bit function (HWB) is of particular interest, since it
seems to be the simplest function with exponential OBDD size.
The complexity of this function with respect to different circuit models,
formulas, and various BDD models is discussed.
},

author = {Bollig, Beate, Löbbing, Martin, Sauerhoff, Martin, Wegener, Ingo},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Complexity; binary decision diagram; OBDD; hidden weighted bit function.; ordered binary decision diagrams},

language = {eng},

month = {3},

number = {2},

pages = {103-115},

publisher = {EDP Sciences},

title = {On the Complexity of the Hidden Weighted Bit Function for Various BDD Models},

url = {http://eudml.org/doc/221977},

volume = {33},

year = {2010},

}

TY - JOUR

AU - Bollig, Beate

AU - Löbbing, Martin

AU - Sauerhoff, Martin

AU - Wegener, Ingo

TI - On the Complexity of the Hidden Weighted Bit Function for Various BDD Models

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 33

IS - 2

SP - 103

EP - 115

AB -
Ordered binary decision diagrams (OBDDs) and several more general BDD models
have turned out to be representations of Boolean functions which are useful
in applications like verification, timing analysis, test pattern generation or
combinatorial optimization.
The hidden weighted bit function (HWB) is of particular interest, since it
seems to be the simplest function with exponential OBDD size.
The complexity of this function with respect to different circuit models,
formulas, and various BDD models is discussed.

LA - eng

KW - Complexity; binary decision diagram; OBDD; hidden weighted bit function.; ordered binary decision diagrams

UR - http://eudml.org/doc/221977

ER -

## References

top- F. Ablayev, Randomization and nondeterminism are incomparable for ordered read-once branching programs, in Proc. of ICALP '97, LNCS1256 (1997) 195-202.
- F. Ablayev and M. Karpinski, On the power of randomized branching programs, in Proc. of ICALP '96, LNCS1099 (1996) 348-356.
- M. Agrawal and T. Thierauf, The satisfiability problem for probabilistic ordered branching programs, in Proc. 13th IEEE Conf. on Computational Complexity (1998) 81-90.
- L. Babai, P. Pudlák, V. Rödl and E. Szemerédi, Lower bounds in complexity of symmetric Boolean functions. Theoret. Comput. Sci.74 (1990) 313-323.
- B. Becker, R. Drechsler and R. Werchner, On the relation between BDDs and FDDs. Inform. and Comput.123 (1997) 185-197.
- B. Bollig and I. Wegener, Partitioned BDDs vs. other BDD models, in Proc. of the Int. Workshop on Logic Synthesis IWLS '97 (1997).
- R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput.35 (1986) 677-691.
- R.E. Bryant, On the complexity of VLSI implementations and graph representations of Boolean functions with applications to integer multiplication. IEEE Trans. Comput.40 (1991) 205-213.
- R.E. Bryant, Symbolic manipulation with ordered binary decision diagrams. ACMComputing Surveys24 (1992) 293-318.
- J. Gergov and C. 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.
- J. Håstad, Almost optimal lower bounds for small depth circuits, in Proc. of 18th STOC (1986) 6-20.
- T. Hofmeister, W. Hohberg and S. Köhling, Some notes on threshold circuits, and multiplication in depth 4. Inform. Process. Lett.39 (1991) 219-225.
- J. Hromkovic, Communication Complexity and Parallel Computing. Springer-Verlag (1997).
- J. Jain, J.A. Abraham, J. Bitner and D.S. Fussell, Probabilistic verification of Boolean functions. Formal Methods in System Design1 (1992) 61-115.
- I. Kremer, N. Nisan and D. Ron, On randomized one-round communication complexity, in Proc. of 27th STOC (1995) 596-605.
- E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).
- M. Löbbing, O. Schröer and I. Wegener, The theory of zero-suppressed BDDs and the number of knight's tours, in Proc. of IFIP Workshop on Applications of the Reed-Muller Expansion on Circuit Design (1995) 38-45.
- A. Narayan, J. Jain, M. Fujita and A. Sangiovanni-Vincentelli, Partitioned ROBDDs--a compact, canonical and efficiently manipulable representation for Boolean functions, in Proc. of ACM/IEEE Int. Conf. on Computer Aided Design ICCAD '96 (1996) 547-554.
- M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. of STACS '98, LNCS1373 (1998) 105-115.
- M. Sauerhoff. Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. of Dortmund (1999).
- M. Sauerhoff, On the size of randomized OBDDs and read-once branching programs for k-stable functions, in Proc. of STACS '99, LNCS1563 (1999) 488-499.
- D. Sieling and I. Wegener, Graph driven BDDs--a new data structure for Boolean functions. Theoret. Comput. Sci.141 (1995) 283-310.
- R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. of 19th STOC (1987) 77-82.
- L.G. Valiant, Short monotone formulae for the majority function. J. Algorithms5 (1984) 363-366.
- S. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams, in Proc. of STACS '97, LNCS1200 (1997) 201-212.
- I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987).

## NotesEmbed ?

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