On maximal QROBDD's of boolean functions
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 677-686.

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

DOI : 10.1051/ita:2005036
Classification : 06E30, 68Q15, 94C10, 94C15
Mots-clés : boolean functions, boolean complexity, boolean graphs, binary decision diagrams, BDD, OBDD 
@article{ITA_2005__39_4_677_0,
     author = {Michon, Jean-Francis and Yun\`es, Jean-Baptiste and Valarcher, Pierre},
     title = {On maximal {QROBDD's} of boolean functions},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {677--686},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     year = {2005},
     doi = {10.1051/ita:2005036},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2005036/}
}
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
SP  - 677
EP  - 686
VL  - 39
IS  - 4
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2005036/
DO  - 10.1051/ita:2005036
LA  - en
ID  - ITA_2005__39_4_677_0
ER  - 
%0 Journal Article
%A Michon, Jean-Francis
%A Yunès, Jean-Baptiste
%A Valarcher, Pierre
%T On maximal QROBDD's of boolean functions
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2005
%P 677-686
%V 39
%N 4
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2005036/
%R 10.1051/ita:2005036
%G en
%F ITA_2005__39_4_677_0
Michon, Jean-Francis; Yunès, Jean-Baptiste; Valarcher, Pierre. On maximal QROBDD's of boolean functions. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 39 (2005) no. 4, pp. 677-686. doi : 10.1051/ita:2005036. http://www.numdam.org/articles/10.1051/ita:2005036/

[1] R.E. Bryant, Graph based algorithms for boolean function manipulation. IEEE Trans. Comput. C-35 (1986) 677-691. | Zbl

[2] C. Gröpl, Binary Decision Diagrams for Random Boolean Functions. Ph.D. Thesis, Humboldt-Universität zu Berlin (1999). | Zbl

[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. | Zbl

[5] M. Heap and M.R. Mercer, Least upper bounds on obdd sizes. IEEE Trans. Comput. 43 (1994) 764-767. | Zbl

[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. | Zbl

[8] I. Wegener, The complexity of Boolean functions. Wiley (1987). | MR | Zbl

[9] I. Wegener, Branching programs and binary decision diagrams. SIAM Monogr. Discrete Math. Appl. (2000). | MR | Zbl

Cité par Sources :