Random Boolean expressions

Danièle Gardy

doi:10.46298/dmtcs.3475

Danièle Gardy - Random Boolean expressions

dmtcs:3475 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05) - https://doi.org/10.46298/dmtcs.3475

Random Boolean expressionsArticle

Authors: Danièle Gardy ¹

1 Parallélisme, Réseaux, Systèmes, Modélisation

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.

https://doi.org/10.46298/dmtcs.3475

Source: HAL:hal-01183339v1

Volume: DMTCS Proceedings vol. AF, Computational Logic and Applications (CLA '05)

Section: Proceedings

Published on: January 1, 2005

Imported on: May 10, 2017

Keywords: Boolean function,complexity,probability distribution for Boolean functions,probability of tautologies,[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]

Bibliographic References

13 Documents citing this article

Florent Koechlin;Pablo Rotondo, Lecture notes in computer science, Analysis of an Efficient Reduction Algorithm for Random Regular Expressions Based on Universality Detection, pp. 206-222, 2021, 10.1007/978-3-030-79416-3_12.

Florent Koechlin;Cyril Nicaud;Pablo Rotondo, Lecture notes in computer science, On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations, pp. 164-177, 2020, 10.1007/978-3-030-48516-0_13, https://doi.org/10.1007/978-3-030-48516-0_13.

Nicolas Broutin;Cécile Mailler, 2018, And/or trees: a local limit point of view, Pure (University of Bath), 10.1002/rsa.20758, https://purehost.bath.ac.uk/ws/files/155617317/andortrees.pdf.

Maciej Bendkowski;Katarzyna Grygiel;Marek Zaionc, Lecture notes in computer science, Asymptotic Properties of Combinatory Logic, pp. 62-72, 2015, 10.1007/978-3-319-17142-5_7.

Antoine Genitrini;Cécile Mailler, Lecture notes in computer science, Equivalence Classes of Random Boolean Trees and Application to the Catalan Satisfiability Problem, pp. 466-477, 2014, 10.1007/978-3-642-54423-1_41.

K. Grygiel;P. M. Idziak;M. Zaionc, 2012, How big is BCI fragment of BCK logic, arXiv (Cornell University), 23, 3, pp. 673-691, 10.1093/logcom/exs017, https://arxiv.org/abs/1112.0643.

Hervé Fournier;Danièle Gardy;Antoine Genitrini;None Bernhard Gittenberger, 2011, The fraction of large random trees representing a given Boolean function in implicational logic, Random Structures and Algorithms, 40, 3, pp. 317-349, 10.1002/rsa.20379.

Nicolas Broutin;Philippe Flajolet, 2011, The distribution of height and diameter in random non‐plane binary trees, arXiv (Cornell University), 41, 2, pp. 215-252, 10.1002/rsa.20393, http://arxiv.org/abs/1009.1515.

Hervé Fournier;Danièle Gardy;Antoine Genitrini;Marek Zaionc, 2010, Tautologies over implication with negative literals, Mathematical logic quarterly, 56, 4, pp. 388-396, 10.1002/malq.200810053.

Antoine Genitrini;Jakub Kozik;Marek Zaionc, Types for Proofs and Programs, Intuitionistic vs. Classical Tautologies, Quantitative Comparison, pp. 100-109, 2008, 10.1007/978-3-540-68103-8_7.

Hervé Fournier;Danièle Gardy;Antoine Genitrini;Bernhard Gittenberger, Lecture notes in computer science, Complexity and Limiting Ratio of Boolean Functions over Implication, pp. 347-362, 2008, 10.1007/978-3-540-85238-4_28.

Zofia Kostrzycka;Marek Zaionc, 2008, Asymptotic Densities in Logic and Type Theory, Studia Logica, 88, 3, pp. 385-403, 10.1007/s11225-008-9110-0.

Hervé Fournier;Danièle Gardy;Antoine Genitrini;Marek Zaionc, Lecture notes in computer science, Classical and Intuitionistic Logic Are Asymptotically Identical, pp. 177-193, 2007, 10.1007/978-3-540-74915-8_16.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 305 times.

This article's PDF has been downloaded 1072 times.