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 journalArticlepeer-review

1 Citation (Scopus)

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 languageEnglish
Pages (from-to)408-446
Number of pages39
JournalApplicable Analysis and Discrete Mathematics
Volume10
Issue number2
DOIs
Publication statusPublished - 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.

Cite this