Associative and commutative tree representations for Boolean functions

2013/05/03 by Antoine Genitrini, Bernhard Gittenberger, Genitrini, Antoine +5
Mathematics · #05A16 #05C05 #06E30 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR #msc:05A16 #msc:05C05 #msc:06E30 #msc:60C05

paper · pdf · doi:10.48550/arxiv.1305.0651

36 pages, 9 figures

arxiv created 2013/05/03 · arxiv updated 2013/05/06

Abstract

Since the 90's, several authors have studied a probability distribution on the set of Boolean functions on n variables induced by some probability distributions on formulas built upon the connectors And and Or and the literals \x₁, x₁, …, x_n, x_n\. These formulas rely on plane binary labelled trees, known as Catalan trees. We extend all the results, in particular the relation between the probability and the complexity of a Boolean function, to other models of formulas: non-binary or non-plane labelled trees (i.e. Polya trees). This includes the natural tree class where associativity and commutativity of the connectors And and Or are realised.

Related

• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
• Generalised and Quotient Models for Random And/Or Trees and Application to Satisfiability
• Variations of the Catalan numbers from some nonassociative binary operations
• Binary trees using the bookshelf and baseball constructions
• Probability Trees