Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. No Shannon effect on ...
Conference paper

No Shannon effect on probability distributions on Boolean functions induced by random expressions

Antoine Genitrini ORCID (1), Bernhard Gittenberger (2)
(1) Parallélisme, Réseaux, Systèmes, Modélisation
(2) Institut für Diskrete Mathematik und Geometrie [Wien]
Download article
Open on HAL
Imported on
January 31, 2017
Published on
December 31, 2009
Last modified on
March 31, 2025
Volume
DMTCS Proceedings vol. AM, 21st International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'10)
Proceedings
DOI
10.46298/dmtcs.2784
License
https://about.hal.science/hal-authorisation-v1
Indicators
543
Views
557
Downloads

No Shannon effect on probability distributions on Boolean functions induced by random expressions

Antoine Genitrini ORCID (1), Bernhard Gittenberger (2)
(1) Parallélisme, Réseaux, Systèmes, Modélisation
(2) Institut für Diskrete Mathematik und Geometrie [Wien]
Abstract
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.
Keywords
  • [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]
  • Boolean functions
  • Implicational expressions
  • Complexity
  • Limiting ratio
  • Galton-Watson trees
  • Probability distribution
  • Analytic combinatorics.
Cited by

Source: OpenCitations

  • Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem

    Authors : Antoine Genitrini ORCID, Cécile Mailler ORCID

    Journal reference : Volume , 2014, pp. 466-477

    DOI : 10.1007/978-3-642-54423-1_41

  • The relation between tree size complexity and probability for Boolean functions generated by uniform random trees

    Applicable Analysis and Discrete Mathematics

    Authors : Veronika Daxner, Antoine Genitrini ORCID, Bernhard Gittenberger ORCID, Cécile Mailler ORCID

    Journal reference : Volume 10, 2016, pp. 408-446

    DOI : 10.2298/aadm160715015d
Preview
Loading PDF preview...