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

Abstract

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

How to cite

top

Bollig, 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
  1. F. Ablayev, Randomization and nondeterminism are incomparable for ordered read-once branching programs, in Proc. of ICALP '97, LNCS1256 (1997) 195-202.  
  2. F. Ablayev and M. Karpinski, On the power of randomized branching programs, in Proc. of ICALP '96, LNCS1099 (1996) 348-356.  
  3. M. Agrawal and T. Thierauf, The satisfiability problem for probabilistic ordered branching programs, in Proc. 13th IEEE Conf. on Computational Complexity (1998) 81-90.  
  4. 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.  
  5. B. Becker, R. Drechsler and R. Werchner, On the relation between BDDs and FDDs. Inform. and Comput.123 (1997) 185-197.  
  6. B. Bollig and I. Wegener, Partitioned BDDs vs. other BDD models, in Proc. of the Int. Workshop on Logic Synthesis IWLS '97 (1997).  
  7. R.E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput.35 (1986) 677-691.  
  8. 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.  
  9. R.E. Bryant, Symbolic manipulation with ordered binary decision diagrams. ACMComputing Surveys24 (1992) 293-318.  
  10. 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.  
  11. J. Håstad, Almost optimal lower bounds for small depth circuits, in Proc. of 18th STOC (1986) 6-20.  
  12. 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.  
  13. J. Hromkovic, Communication Complexity and Parallel Computing. Springer-Verlag (1997).  
  14. J. Jain, J.A. Abraham, J. Bitner and D.S. Fussell, Probabilistic verification of Boolean functions. Formal Methods in System Design1 (1992) 61-115.  
  15. I. Kremer, N. Nisan and D. Ron, On randomized one-round communication complexity, in Proc. of 27th STOC (1995) 596-605.  
  16. E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997).  
  17. 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.  
  18. 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.  
  19. M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. of STACS '98, LNCS1373 (1998) 105-115.  
  20. M. Sauerhoff. Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. of Dortmund (1999).  
  21. 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.  
  22. D. Sieling and I. Wegener, Graph driven BDDs--a new data structure for Boolean functions. Theoret. Comput. Sci.141 (1995) 283-310.  
  23. R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. of 19th STOC (1987) 77-82.  
  24. L.G. Valiant, Short monotone formulae for the majority function. J. Algorithms5 (1984) 363-366.  
  25. S. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams, in Proc. of STACS '97, LNCS1200 (1997) 201-212.  
  26. I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987).  

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.