# On maximal QROBDD’s of boolean functions

Jean-Francis Michon; Jean-Baptiste Yunès; Pierre Valarcher

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2005)

- Volume: 39, Issue: 4, page 677-686
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topMichon, Jean-Francis, Yunès, Jean-Baptiste, and Valarcher, Pierre. "On maximal QROBDD’s of boolean functions." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 39.4 (2005): 677-686. <http://eudml.org/doc/245366>.

@article{Michon2005,

abstract = {We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).},

author = {Michon, Jean-Francis, Yunès, Jean-Baptiste, Valarcher, Pierre},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

keywords = {boolean functions; boolean complexity; boolean graphs; binary decision diagrams; BDD; OBDD},

language = {eng},

number = {4},

pages = {677-686},

publisher = {EDP-Sciences},

title = {On maximal QROBDD’s of boolean functions},

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

volume = {39},

year = {2005},

}

TY - JOUR

AU - Michon, Jean-Francis

AU - Yunès, Jean-Baptiste

AU - Valarcher, Pierre

TI - On maximal QROBDD’s of boolean functions

JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

PY - 2005

PB - EDP-Sciences

VL - 39

IS - 4

SP - 677

EP - 686

AB - We investigate the structure of “worst-case” quasi reduced ordered decision diagrams and Boolean functions whose truth tables are associated to: we suggest different ways to count and enumerate them. We, then, introduce a notion of complexity which leads to the concept of “hard” Boolean functions as functions whose QROBDD are “worst-case” ones. So we exhibit the relation between hard functions and the Storage Access function (also known as Multiplexer).

LA - eng

KW - boolean functions; boolean complexity; boolean graphs; binary decision diagrams; BDD; OBDD

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

ER -

## References

top- [1] R.E. Bryant, Graph based algorithms for boolean function manipulation. IEEE Trans. Comput. C-35 (1986) 677–691. Zbl0593.94022
- [2] C. Gröpl, Binary Decision Diagrams for Random Boolean Functions. Ph.D. Thesis, Humboldt-Universität zu Berlin (1999). Zbl1023.94022
- [3] C. Gröpl, H.J. Prömel and A. Srivastav, Size and structure of random ordered binary decision diagrams (extended abstract), in STACS’98, Springer Verlag. Lect. Notes Comput. Sci. 1373 (1998) 238–248.
- [4] C. Gröpl, H.J. Prömel and A. Srivastav, On the evolution of the worst-case obdd size. Inform. Process. Lett. 77 (2001) 1–7. Zbl1003.68050
- [5] M. Heap and M.R. Mercer, Least upper bounds on obdd sizes. IEEE Trans. Comput. 43 (1994) 764–767. Zbl1033.68682
- [6] J.F. Michon, P. Valarcher and J.B. Yunès, Integer sequence number a100344. stored in The On-Line Encyclopedia of Integer Sequence, N.J.A. Sloane, published electronically at http://www.research.att.com/~njas/sequences (2004).
- [7] W. Paul, A $2.5n$ lower bound on the combinatorial complexity of boolean functions. SIAM J. Comput. 6 (1977) 427–443. Zbl0358.68081
- [8] I. Wegener, The complexity of Boolean functions. Wiley (1987). Zbl0623.94018MR905473
- [9] I. Wegener, Branching programs and binary decision diagrams. SIAM Monogr. Discrete Math. Appl. (2000). Zbl0956.68068MR1775233

## NotesEmbed ?

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