On maximal QROBDD's of Boolean functions
Jean-Francis Michon; Jean-Baptiste Yunès; Pierre Valarcher
RAIRO - Theoretical Informatics and Applications (2010)
- Volume: 39, Issue: 4, page 677-686
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topMichon, Jean-Francis, Yunès, Jean-Baptiste, and Valarcher, Pierre. "On maximal QROBDD's of Boolean functions." RAIRO - Theoretical Informatics and Applications 39.4 (2010): 677-686. <http://eudml.org/doc/92784>.
@article{Michon2010,
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},
keywords = {Boolean functions; Boolean complexity; Boolean graphs; binary decision diagrams; BDD; OBDD},
language = {eng},
month = {3},
number = {4},
pages = {677-686},
publisher = {EDP Sciences},
title = {On maximal QROBDD's of Boolean functions},
url = {http://eudml.org/doc/92784},
volume = {39},
year = {2010},
}
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
DA - 2010/3//
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/92784
ER -
References
top- R.E. Bryant, Graph based algorithms for boolean function manipulation. IEEE Trans. Comput.C-35 (1986) 677–691.
- C. Gröpl, Binary Decision Diagrams for Random Boolean Functions. Ph.D. Thesis, Humboldt-Universität zu Berlin (1999).
- 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.
- 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.
- M. Heap and M.R. Mercer, Least upper bounds on obdd sizes. IEEE Trans. Comput.43 (1994) 764–767.
- 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 (2004). URIhttp://www.research.att.com/~njas/sequences
- W. Paul, A 2.5n lower bound on the combinatorial complexity of boolean functions. SIAM J. Comput.6 (1977) 427–443.
- I. Wegener, The complexity of Boolean functions. Wiley (1987).
- I. Wegener, Branching programs and binary decision diagrams. 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.