Geodesic
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

Voir la notice de l'article provenant de la source Numdam

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
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :