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

Fingerprint

Quotient
Model
Equivalence relation
Saturation
Infinity
Tend
Generalise
Integer

Keywords

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

Cite this

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

In: Algorithmica, Vol. 76, No. 4, 12.2016, p. 1106–1138.

Research output: Contribution to journalArticle

@article{bccb636d4faf402f9304fc35e5fed0d9,
title = "Generalised and quotient models for random and/or trees and application to satisfiability",
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.).",
keywords = "Analytic combinatorics, Boolean formulas/functions, Catalan trees, Equivalence relation, Probability distribution, Satisfiability",
author = "Antoine Genitrini and C{\'e}cile Mailler",
year = "2016",
month = "12",
doi = "10.1007/s00453-016-0113-3",
language = "English",
volume = "76",
pages = "1106–1138",
journal = "Algorithmica",
issn = "0178-4617",
publisher = "Springer New York",
number = "4",

}

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 -