Associative and commutative tree representations for Boolean functions

Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus, Cécile Mailler

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

Since the 1990s, the probability distribution on Boolean functions, induced by some random formulas built upon the connectives And and Or, has been intensively studied. These formulas rely on plane binary trees. We extend all the results, in particular the relation between the probability and the complexity of a function, to more general formula structures: non-binary or non-plane trees. These formulas satisfy the natural properties of associativity and commutativity.

Original languageEnglish
Pages (from-to)70-101
Number of pages32
JournalTheoretical Computer Science
Volume570
Issue numberC
Early online date7 Jan 2015
DOIs
Publication statusPublished - 9 Mar 2015

Keywords

  • Analytic combinatorics
  • Asymptotic ratio
  • Boolean functions
  • Probability distribution
  • Random boolean formulas
  • Random trees

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Associative and commutative tree representations for Boolean functions'. Together they form a unique fingerprint.

Cite this