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 expressionsConference paper

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

Bibliographic References

15 Documents citing this article

L. Aslanyan, 2023, Logic Separation: Discrete Modelling of Pattern Recognition, Pattern Recognition and Image Analysis, 33, 4, pp. 902-936, 10.1134/s1054661823040077.

Zofia Kostrzycka;Marek Zaionc, 2023, Fuzzy logics – quantitatively, Journal of Applied Non-Classical Logics, 34, 1, pp. 97-132, 10.1080/11663081.2023.2269645.

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

Florent Koechlin;Cyril Nicaud;Pablo Rotondo, 2020, On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations, Lecture notes in computer science, pp. 164-177, 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, arXiv (Cornell University), 53, 1, pp. 15-58, 10.1002/rsa.20758, http://arxiv.org/abs/1510.06691.

Maciej Bendkowski;Katarzyna Grygiel;Marek Zaionc, 2015, Asymptotic Properties of Combinatory Logic, Homo Politicus (Academy of Humanities and Economics in Lodz), pp. 62-72, 10.1007/978-3-319-17142-5_7, http://ruj.uj.edu.pl/xmlui/handle/item/19598.

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

K. Grygiel;P. M. Idziak;M. Zaionc, 2012, How big is BCI fragment of BCK logic, Homo Politicus (Academy of Humanities and Economics in Lodz), 23, 3, pp. 673-691, 10.1093/logcom/exs017, http://ruj.uj.edu.pl/xmlui/handle/item/68.

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;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, Homo Politicus (Academy of Humanities and Economics in Lodz), 56, 4, pp. 388-396, 10.1002/malq.200810053, https://ruj.uj.edu.pl/xmlui/handle/item/165732.

Antoine Genitrini;Jakub Kozik;Marek Zaionc, 2008, Intuitionistic vs. Classical Tautologies, Quantitative Comparison, Lecture notes in computer science, pp. 100-109, 10.1007/978-3-540-68103-8_7.

Hervé Fournier;Danièle Gardy;Antoine Genitrini;Bernhard Gittenberger, 2008, Complexity and Limiting Ratio of Boolean Functions over Implication, Lecture notes in computer science, pp. 347-362, 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, 2007, Classical and Intuitionistic Logic Are Asymptotically Identical, Lecture notes in computer science, pp. 177-193, 10.1007/978-3-540-74915-8_16.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 457 times.

This article's PDF has been downloaded 3027 times.