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 expressions
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]
9 Documents citing this article
Source : OpenCitations
Bendkowski, Maciej; Grygiel, Katarzyna; Zaionc, Marek, 2015, Asymptotic Properties Of Combinatory Logic, Lecture Notes In Computer Science, pp. 62-72, 10.1007/978-3-319-17142-5_7.
Broutin, Nicolas; Flajolet, Philippe, 2011, The Distribution Of Height And Diameter In Random Non-Plane Binary Trees, Random Structures And Algorithms, 41, 2, pp. 215-252, 10.1002/rsa.20393.
Broutin, Nicolas; Mailler, CĂŠcile, 2018, And/or Trees: A Local Limit Point Of View, Random Structures And Algorithms, 53, 1, pp. 15-58, 10.1002/rsa.20758.
Fournier, Hervé; Gardy, Danièle; Genitrini, Antoine; Zaionc, Marek, 2010, Tautologies Over Implication With Negative Literals, Zeitschrift Für Mathematische Logik Und Grundlagen Der Mathematik, 56, 4, pp. 388-396, 10.1002/malq.200810053.
Fournier, HervĂŠ; Gardy, Danièle; Genitrini, Antoine; Gittenberger, Bernhard, 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.
Genitrini, Antoine; Kozik, Jakub; Zaionc, Marek, Intuitionistic Vs. Classical Tautologies, Quantitative Comparison, Lecture Notes In Computer Science, pp. 100-109, 10.1007/978-3-540-68103-8_7.
Genitrini, Antoine; Mailler, CĂŠcile, 2014, Equivalence Classes Of Random Boolean Trees And Application To The Catalan Satisfiability Problem, LATIN 2014: Theoretical Informatics, pp. 466-477, 10.1007/978-3-642-54423-1_41.
Koechlin, Florent; Nicaud, Cyril; Rotondo, Pablo, 2020, On The Degeneracy Of Random Expressions Specified By Systems Of Combinatorial Equations, Developments In Language Theory, pp. 164-177, 10.1007/978-3-030-48516-0_13.
Kostrzycka, Zofia; Zaionc, Marek, 2008, Asymptotic Densities In Logic And Type Theory, Studia Logica, 88, 3, pp. 385-403, 10.1007/s11225-008-9110-0.