Geodesic
And/or tree probabilities of Boolean functions
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005).

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

We consider two probability distributions on Boolean functions defined in terms of their representations by $\texttt{and/or}$ trees (or formulas). The relationships between them, and connections with the complexity of the function, are studied. New and improved bounds on these probabilities are given for a wide class of functions, with special attention being paid to the constant function $\textit{True}$ and read-once functions in a fixed number of variables. 
@article{DMTCS_2005_special_249_a3,
     author = {Gardy, Dani\`ele and Woods, Alan},
     title = {And/or tree probabilities of {Boolean} functions},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms},
     year = {2005},
     doi = {10.46298/dmtcs.3355},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3355/}
}
TY  - JOUR
AU  - Gardy, Danièle
AU  - Woods, Alan
TI  - And/or tree probabilities of Boolean functions
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3355/
DO  - 10.46298/dmtcs.3355
LA  - en
ID  - DMTCS_2005_special_249_a3
ER  - 
%0 Journal Article
%A Gardy, Danièle
%A Woods, Alan
%T And/or tree probabilities of Boolean functions
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3355/
%R 10.46298/dmtcs.3355
%G en
%F DMTCS_2005_special_249_a3
Gardy, Danièle; Woods, Alan. And/or tree probabilities of Boolean functions. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms, DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms (2005). doi : 10.46298/dmtcs.3355. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3355/

Cité par Sources :