Projects per year
Abstract
This article is motivated by the following satisfiability question: pick uniformly at random an (Formula presented.) Boolean expression of length n, built on a set of (Formula presented.) Boolean variables. What is the probability that this expression is satisfiable? asymptotically when n tends to infinity? The model of random Boolean expressions developed in the present paper is the model of Boolean Catalan trees, already extensively studied in the literature for a constant sequence (Formula presented.). The fundamental breakthrough of this paper is to generalise the previous results for any (reasonable) sequence of integers (Formula presented.), which enables us, in particular, to solve the above satisfiability question. We also analyse the effect of introducing a natural equivalence relation on the set of Boolean expressions. This new quotient model happens to exhibit a very interesting threshold (or saturation) phenomena at (Formula presented.).
Original language  English 

Pages (fromto)  1106–1138 
Number of pages  33 
Journal  Algorithmica 
Volume  76 
Issue number  4 
Early online date  12 Jan 2016 
DOIs  
Publication status  Published  Dec 2016 
Keywords
 Analytic combinatorics
 Boolean formulas/functions
 Catalan trees
 Equivalence relation
 Probability distribution
 Satisfiability
Fingerprint Dive into the research topics of 'Generalised and quotient models for random and/or trees and application to satisfiability'. Together they form a unique fingerprint.
Projects
 1 Finished

Emergence of Condensation in Stochastic Systems
Morters, P.
Engineering and Physical Sciences Research Council
1/08/13 → 31/08/16
Project: Research council