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

Abstract

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

How to cite

top

Michon, 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
  1. R.E. Bryant, Graph based algorithms for boolean function manipulation. IEEE Trans. Comput.C-35 (1986) 677–691.  
  2. C. Gröpl, Binary Decision Diagrams for Random Boolean Functions. Ph.D. Thesis, Humboldt-Universität zu Berlin (1999).  
  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.  
  5. M. Heap and M.R. Mercer, Least upper bounds on obdd sizes. IEEE Trans. Comput.43 (1994) 764–767.  
  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 (2004).  URIhttp://www.research.att.com/~njas/sequences
  7. W. Paul, A 2.5n lower bound on the combinatorial complexity of boolean functions. SIAM J. Comput.6 (1977) 427–443.  
  8. I. Wegener, The complexity of Boolean functions. Wiley (1987).  
  9. I. Wegener, Branching programs and binary decision diagrams. SIAM Monogr. Discrete Math. Appl. (2000).  

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.