The relation between tree size complexity and probability for boolean functions generated by uniform random trees

Veronika Daxner; Antoine Genitrini; Bernhard Gittenberger; Cecile Mailler

doi:10.2298/AADM160715015D

The relation between tree size complexity and probability for boolean functions generated by uniform random trees

Veronika Daxner, Antoine Genitrini, Bernhard Gittenberger, Cecile Mailler

Research output: Contribution to journal › Article › peer-review

1 Citation (SciVal)

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	https://doi.org/10.2298/AADM160715015D
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

Access to Document

10.2298/AADM160715015D

Cite this

@article{7bd3604db695445d87b64d0eb5a1447b,

title = "The relation between tree size complexity and probability for boolean functions generated by uniform random trees",

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.",

keywords = "Analytic combinatorics, Boolean functions, Probability distribution, Random Boolean formulas, Tree size complexity",

author = "Veronika Daxner and Antoine Genitrini and Bernhard Gittenberger and Cecile Mailler",

year = "2016",

month = jan,

day = "1",

doi = "10.2298/AADM160715015D",

language = "English",

volume = "10",

pages = "408--446",

journal = "Applicable Analysis and Discrete Mathematics",

issn = "1452-8630",

publisher = "University of Belgrade",

number = "2",

}

TY - JOUR

T1 - The relation between tree size complexity and probability for boolean functions generated by uniform random trees

AU - Daxner, Veronika

AU - Genitrini, Antoine

AU - Gittenberger, Bernhard

AU - Mailler, Cecile

PY - 2016/1/1

Y1 - 2016/1/1

N2 - 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.

AB - 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.

KW - Analytic combinatorics

KW - Boolean functions

KW - Probability distribution

KW - Random Boolean formulas

KW - Tree size complexity

UR - http://www.scopus.com/inward/record.url?scp=85008191097&partnerID=8YFLogxK

U2 - 10.2298/AADM160715015D

DO - 10.2298/AADM160715015D

M3 - Article

AN - SCOPUS:85008191097

VL - 10

SP - 408

EP - 446

JO - Applicable Analysis and Discrete Mathematics

JF - Applicable Analysis and Discrete Mathematics

SN - 1452-8630

IS - 2

ER -

The relation between tree size complexity and probability for boolean functions generated by uniform random trees

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this