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]

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, Springer eBooks, 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), 53, 1, pp. 15-58, 10.1002/rsa.20758, https://researchportal.bath.ac.uk/en/publications/12438f58-cc75-4317-9495-6900b69794d3.

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.

Katarzyna Grygiel;Paweł M. Idziak;Marek 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;Antoine Genitrini Bernhard Gittenberger, 2011, The fraction of large random trees representing a given Boolean function in implicational logic, Random Structures & 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, Springer eBooks, 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 197 times.

This article's PDF has been downloaded 872 times.