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

Antoine Genitrini, Cécile Mailler

Research output: Contribution to journalArticle

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)1106–1138
Number of pages33
JournalAlgorithmica
Volume76
Issue number4
Early online date12 Jan 2016
DOIs
Publication statusPublished - 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

  • Cite this