Geodesic
Probabilities of Boolean functions given by random implicational formulas
Antoine Genitrini1 ; Bernhard Gittenberger2 ; Veronika Kraus3 ; Cécile Mailler4
1Université Pierre et Marie Curie
2Technische Universität Wien
3Institute of Bioinformatics and Translational Research
4Université de Versailles Saint-Quentin
The electronic journal of combinatorics, Tome 19 (2012) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We study the asymptotic relation between the probability and the complexity of Boolean functions in the implicational fragment which are generated by large random Boolean expressions involving variables and implication, as the number of variables tends to infinity. In contrast to models studied in the literature so far, we consider two expressions to be equal if they differ only in the order of the premises. A precise asymptotic formula is derived for functions of low complexity. Furthermore, we show that this model does not exhibit the Shannon effect.An erratum was added to this paper on Feb 20, 2014.
DOI : 10.37236/2402
Classification : 03B05, 05A16, 06E30, 60C05
Mots-clés : Boolean functions, Boolean formulas, analytic combinatorics, complexity, Shannon effect, implicational fragment, random Boolean expressions

Antoine Genitrini  1   ; Bernhard Gittenberger  2   ; Veronika Kraus  3   ; Cécile Mailler  4

1 Université Pierre et Marie Curie
2 Technische Universität Wien
3 Institute of Bioinformatics and Translational Research
4 Université de Versailles Saint-Quentin 
@article{10_37236_2402,
     author = {Antoine Genitrini and Bernhard Gittenberger and Veronika Kraus and C\'ecile Mailler},
     title = {Probabilities of {Boolean} functions given by random implicational formulas},
     journal = {The electronic journal of combinatorics},
     year = {2012},
     volume = {19},
     number = {2},
     doi = {10.37236/2402},
     zbl = {1243.03011},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/2402/}
}
TY  - JOUR
AU  - Antoine Genitrini
AU  - Bernhard Gittenberger
AU  - Veronika Kraus
AU  - Cécile Mailler
TI  - Probabilities of Boolean functions given by random implicational formulas
JO  - The electronic journal of combinatorics
PY  - 2012
VL  - 19
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/2402/
DO  - 10.37236/2402
ID  - 10_37236_2402
ER  - 
%0 Journal Article
%A Antoine Genitrini
%A Bernhard Gittenberger
%A Veronika Kraus
%A Cécile Mailler
%T Probabilities of Boolean functions given by random implicational formulas
%J The electronic journal of combinatorics
%D 2012
%V 19
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/2402/
%R 10.37236/2402
%F 10_37236_2402
Antoine Genitrini; Bernhard Gittenberger; Veronika Kraus; Cécile Mailler. Probabilities of Boolean functions given by random implicational formulas. The electronic journal of combinatorics, Tome 19 (2012) no. 2. doi: 10.37236/2402

Cité par Sources :