Abstract
An associative Boolean tree is a plane rooted tree whose internal nodes are labelled by and or or and whose leaves are labelled by literals taken from a fixed set of variables and their negations. We study the distribution induced on the set of Boolean functions by the uniform distribution on the set of associative trees of a large fixed size, where the size of a tree is defined as the number of its nodes. Using analytic combinatorics, we prove a relation between the probability of a given function and its tree size complexity.
Original language | English |
---|---|
Pages (from-to) | 408-446 |
Number of pages | 39 |
Journal | Applicable Analysis and Discrete Mathematics |
Volume | 10 |
Issue number | 2 |
DOIs | |
Publication status | Published - 1 Jan 2016 |
Keywords
- Analytic combinatorics
- Boolean functions
- Probability distribution
- Random Boolean formulas
- Tree size complexity
ASJC Scopus subject areas
- Analysis
- Discrete Mathematics and Combinatorics
- Applied Mathematics