### 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 (from-to) | 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 |

### Fingerprint

### Keywords

- Analytic combinatorics
- Boolean formulas/functions
- Catalan trees
- Equivalence relation
- Probability distribution
- Satisfiability

### Cite this

*Algorithmica*,

*76*(4), 1106–1138. https://doi.org/10.1007/s00453-016-0113-3

**Generalised and quotient models for random and/or trees and application to satisfiability.** / Genitrini, Antoine; Mailler, Cécile.

Research output: Contribution to journal › Article

*Algorithmica*, vol. 76, no. 4, pp. 1106–1138. https://doi.org/10.1007/s00453-016-0113-3

}

TY - JOUR

T1 - Generalised and quotient models for random and/or trees and application to satisfiability

AU - Genitrini, Antoine

AU - Mailler, Cécile

PY - 2016/12

Y1 - 2016/12

N2 - 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.).

AB - 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.).

KW - Analytic combinatorics

KW - Boolean formulas/functions

KW - Catalan trees

KW - Equivalence relation

KW - Probability distribution

KW - Satisfiability

UR - http://www.scopus.com/inward/record.url?scp=84954314227&partnerID=8YFLogxK

UR - http://dx.doi.org/10.1007/s00453-016-0113-3

U2 - 10.1007/s00453-016-0113-3

DO - 10.1007/s00453-016-0113-3

M3 - Article

VL - 76

SP - 1106

EP - 1138

JO - Algorithmica

JF - Algorithmica

SN - 0178-4617

IS - 4

ER -