 |
Discrete Mathematics & Theoretical Computer Science |
Antoine Genitrini ; Bernhard Gittenberger - No Shannon effect on probability distributions on Boolean functions induced by random expressions
dmtcs:2784 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10) - https://doi.org/10.46298/dmtcs.2784No Shannon effect on probability distributions on Boolean functions induced by random expressionsArticle
Authors: Antoine Genitrini 
1; Bernhard Gittenberger 2
- 1 Parallélisme, Réseaux, Systèmes, Modélisation
- 2 Institut für Diskrete Mathematik und Geometrie [Wien]
The Shannon effect states that "almost all'' Boolean functions have a complexity close to the maximal possible for the uniform probability distribution. In this paper we use some probability distributions on functions, induced by random expressions, and prove that this model does not exhibit the Shannon effect.
Source: HAL:hal-01185582v1
Volume: DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Section: Proceedings
Published on: January 1, 2010
Imported on: January 31, 2017
Keywords: Analytic combinatorics.,Probability distribution,Boolean functions,Implicational expressions,Complexity,Limiting ratio,Galton-Watson trees,[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO],[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[INFO.INFO-CG] Computer Science [cs]/Computational Geometry [cs.CG]
2 Documents citing this article
Consultation statistics
This page has been seen 227 times.
This article's PDF has been downloaded 241 times.