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. Random Boolean expre ...
Conference paper

Random Boolean expressions

Danièle Gardy ORCID (1)
(1) Parallélisme, Réseaux, Systèmes, Modélisation
Download article
Open on HAL
Imported on
May 10, 2017
Published on
December 31, 2004
Last modified on
March 31, 2025
Volume 0
DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)
Proceedings
DOI
10.46298/dmtcs.3475
License
https://about.hal.science/hal-authorisation-v1
Indicators
633
Views
3837
Downloads

Random Boolean expressions

Danièle Gardy ORCID (1)
(1) Parallélisme, Réseaux, Systèmes, Modélisation
Abstract
We examine how we can define several probability distributions on the set of Boolean functions on a fixed number of variables, starting from a representation of Boolean expressions by trees. Analytic tools give us a systematic way to prove the existence of probability distributions, the main challenge being the actual computation of the distributions. We finally consider the relations between the probability of a Boolean function and its complexity.
Keywords
  • [INFO.INFO-LO]Computer Science [cs]/Logic in Computer Science [cs.LO]
  • [INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
  • [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC]
  • Boolean function
  • complexity
  • probability distribution for Boolean functions
  • probability of tautologies
Cited by

Source: OpenCitations

  • How big is BCI fragment of BCK logic

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : K. Grygiel, P. M. Idziak, M. Zaionc ORCID

    Journal reference : Volume 23, 2012, pp. 673-691

    DOI : 10.1093/logcom/exs017
  • Tautologies over implication with negative literals

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Marek Zaionc ORCID

    Journal reference : Volume 56, 2010, pp. 388-396

    DOI : 10.1002/malq.200810053
  • On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations

    Lecture notes in computer science

    Authors : Florent Koechlin ORCID, Cyril Nicaud ORCID, Pablo Rotondo ORCID

    Journal reference : Volume , 2020, pp. 164-177

    DOI : 10.1007/978-3-030-48516-0_13
  • The distribution of height and diameter in random non‐plane binary trees

    arXiv (Cornell University)

    Authors : Nicolas Broutin, Philippe Flajolet

    Journal reference : Volume 41, 2011, pp. 215-252

    DOI : 10.1002/rsa.20393
  • Asymptotic Properties of Combinatory Logic

    Jagiellonian University Repository (Jagiellonian University)

    Authors : Maciej Bendkowski, Katarzyna Grygiel, Marek Zaionc ORCID

    Journal reference : Volume , 2015, pp. 62-72

    DOI : 10.1007/978-3-319-17142-5_7
  • Intuitionistic vs. Classical Tautologies, Quantitative Comparison

    Lecture notes in computer science

    Authors : Antoine Genitrini ORCID, Jakub Kozik ORCID, Marek Zaionc ORCID

    Journal reference : Volume , 2008, pp. 100-109

    DOI : 10.1007/978-3-540-68103-8_7
  • Complexity and Limiting Ratio of Boolean Functions over Implication

    Lecture notes in computer science

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume , 2008, pp. 347-362

    DOI : 10.1007/978-3-540-85238-4_28
  • On the Potential of Deep Symbolic Models for Classification Problems

    Lecture notes in computer science

    Authors : Florian Beck ORCID, Johannes Fürnkranz ORCID, Van Quoc Phuong Huynh ORCID

    Journal reference : Volume , 2025, pp. 161-175

    DOI : 10.1007/978-3-032-05461-6_11
  • And/or trees: A local limit point of view

    arXiv (Cornell University)

    Authors : Nicolas Broutin, Cécile Mailler ORCID

    Journal reference : Volume 53, 2018, pp. 15-58

    DOI : 10.1002/rsa.20758
  • Fuzzy logics – quantitatively

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Zofia Kostrzycka ORCID, Marek Zaionc ORCID

    Journal reference : Volume 34, 2023, pp. 97-132

    DOI : 10.1080/11663081.2023.2269645
  • 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
  • Classical and Intuitionistic Logic Are Asymptotically Identical

    Lecture notes in computer science

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Marek Zaionc ORCID

    Journal reference : Volume , 2007, pp. 177-193

    DOI : 10.1007/978-3-540-74915-8_16
  • Logic Separation: Discrete Modelling of Pattern Recognition

    Pattern Recognition and Image Analysis

    Authors : L. Aslanyan ORCID

    Journal reference : Volume 33, 2023, pp. 902-936

    DOI : 10.1134/s1054661823040077
  • The fraction of large random trees representing a given Boolean function in implicational logic

    Random Structures and Algorithms

    Authors : Hervé Fournier, Danièle Gardy ORCID, Antoine Genitrini ORCID, Bernhard Gittenberger ORCID

    Journal reference : Volume 40, 2011, pp. 317-349

    DOI : 10.1002/rsa.20379
  • Asymptotic Densities in Logic and Type Theory

    Homo Politicus (Academy of Humanities and Economics in Lodz)

    Authors : Zofia Kostrzycka ORCID, Marek Zaionc ORCID

    Journal reference : Volume 88, 2008, pp. 385-403

    DOI : 10.1007/s11225-008-9110-0
  • Analysis of an Efficient Reduction Algorithm for Random Regular Expressions Based on Universality Detection

    Authors : Florent Koechlin ORCID, Pablo Rotondo ORCID

    Journal reference : Volume , 2021, pp. 206-222

    DOI : 10.1007/978-3-030-79416-3_12
Preview
Loading PDF preview...