The Relation between Tree Size Complexity and Probability for Boolean Functions Generated by Uniform Random Trees

Applicable Analysis and Discrete Mathematics

article

Veronika Daxner¹  Antoine Genitrini²  Bernhard Gittenberger¹  Cécile Mailler³ 

[1] Technische Universit¨at Wien;Sorbonne Universit´es;Department of Mathematical Sciences, University of Bath

关键词: Boolean functions;    Probability distribution;    Random Boolean formulas;    Tree size complexity;    Analytic combinatorics;   

DOI  :  10.2298/AADM160715015D

学科分类：社会科学、人文和艺术（综合）

来源: Univerzitet u Beogradu * Elektrotehnicki Fakultet / University of Belgrade, Faculty of Electrical Engineering

【 摘 要 】

An associative Boolean tree is a plane rooted tree whose internal nodes arelabelled by and or or and whose leaves are labelled by literals taken from afixed set of variables and their negations. We study the distribution inducedon the set of Boolean functions by the uniform distribution on the set ofassociative trees of a large fixed size, where the size of a tree is defined asthe number of its nodes. Using analytic combinatorics, we prove a relationbetween the probability of a given function and its tree size complexity.

【 授权许可】

Unknown