Projects per year
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 (fromto)  408446 
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
Fingerprint
Dive into the research topics of 'The relation between tree size complexity and probability for boolean functions generated by uniform random trees'. Together they form a unique fingerprint.Projects
 1 Finished

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