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
0000-0001-6425-4585
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.
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.
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.
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, https://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.