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 - Informatique Théorique et Applications (1999)

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

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 - Informatique Théorique et Applications 33.2 (1999): 103-115. <http://eudml.org/doc/92593>.

@article{Bollig1999,
author = {Bollig, Beate, Löbbing, Martin, Sauerhoff, Martin, Wegener, Ingo},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {ordered binary decision diagrams},
language = {eng},
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/92593},
volume = {33},
year = {1999},
}

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 - Informatique Théorique et Applications
PY - 1999
PB - EDP-Sciences
VL - 33
IS - 2
SP - 103
EP - 115
LA - eng
KW - ordered binary decision diagrams
UR - http://eudml.org/doc/92593
ER -

References

top
  1. [1] F. Ablayev, Randomization and nondeterminism are incomparable for ordered read-once branching programs, in Proc. of ICALP '97, LNCS 1256 (1997) 195-202. MR1616185
  2. [2] F. Ablayev and M. Karpinski, On the power of randomized branching programs, in Proc. of ICALP '96, LNCS 1099 (1996) 348-356. Zbl1046.68531MR1464462
  3. [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. Zbl0935.68025MR1655683
  4. [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. Zbl0701.68044MR1073767
  5. [5] B. Becker, R. Drechsler and R. Werchner, On the relation between BDDs and FDDs. Inform. and Comput. 123 (1997) 185-197. Zbl0839.68022MR1362665
  6. [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. [7] R. E. Bryant, Graph-based algorithms for Boolean function manipulation. IEEE Trans. Comput. 35 (1986) 677-691. Zbl0593.94022
  8. [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. Zbl1220.68060MR1094031
  9. [9] R. E. Bryant, Symbolic manipulation with ordered binary decision diagrams. ACM Computing Surveys 24 (1992) 293-318. 
  10. [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 Design 8 (1996) 273-282. 
  11. [11] J. Hastad, Almost optimal lower bounds for small depth circuits, in Proc. of 18th STOC (1986) 6-20. 
  12. [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. Zbl0735.68038MR1130753
  13. [13] J. Hromkovič, Communication Complexity and Parallel Computing. Springer-Verlag (1997). Zbl0873.68098MR1442518
  14. [14] J. Jain, J. A. Abraham J. Bitner and D. S. Fussell, Probabilistic verification of Boolean functions. Formal Methods in System Design 1 (1992) 61-115. Zbl0777.94021
  15. [15] I. Kremer, N. Nisan and D. Ron, On randomized one-round communication complexity, in Proc. of 27th STOC (1995) 596-605. Zbl0926.94022
  16. [16] E. Kushilevitz and N. Nisan, Communication Complexity. Cambridge University Press (1997). Zbl0869.68048MR1426129
  17. [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. [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. [19] M. Sauerhoff, Lower bounds for randomized read-k-times branching programs, in Proc. of STACS '98, LNCS 1373 (1998) 105-115. MR1650785
  20. [20] M. Sauerhoff. Complexity Theoretical Results for Randomized Branching Programs. PhD thesis, Univ. of Dortmund (1999). 
  21. [21] M. Sauerhoff, On the size of randomized OBDDs and read-once branching programs for k-stable functions, in Proc. of STACS '99, LNCS 1563 (1999) 488-499. MR1734076
  22. [22] D. Sieling and I. Wegener, Graph driven BDDs- a new data structure for Boolean functions. Theoret. Comput. Sci. 141 (1995) 283-310. Zbl0873.68036MR1323158
  23. [23] R. Smolensky, Algebraic methods in the theory of lower bounds for Boolean circuit complexity, in Proc. of 19th STOC (1987) 77-82. 
  24. [24] L.G. Valiant, Short monotone formulae for the majority function. J. Algorithms 5 (1984) 363-366. Zbl0554.94017MR756162
  25. [25] S. Waack, On the descriptive and algorithmic power of parity ordered binary decision diagrams, in Proc. of STACS '97, LNCS 1200 (1997) 201-212. MR1473775
  26. [26] I. Wegener, The Complexity of Boolean Functions. Wiley-Teubner (1987). Zbl0623.94018MR905473

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.