Associative and commutative tree representations for Boolean functions

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

doi:10.1016/j.tcs.2014.12.025

Associative and commutative tree representations for Boolean functions

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

Technische Universität Wien

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

7 Citations (SciVal)

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 language	English
Pages (from-to)	70-101
Number of pages	32
Journal	Theoretical Computer Science
Volume	570
Issue number	C
Early online date	7 Jan 2015
DOIs	https://doi.org/10.1016/j.tcs.2014.12.025
Publication status	Published - 9 Mar 2015

Keywords

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1016/j.tcs.2014.12.025

Cite this

@article{9d01f603df224765aa7b7858c010fdb3,

title = "Associative and commutative tree representations for Boolean functions",

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

keywords = "Analytic combinatorics, Asymptotic ratio, Boolean functions, Probability distribution, Random boolean formulas, Random trees",

author = "Antoine Genitrini and Bernhard Gittenberger and Veronika Kraus and C{\'e}cile Mailler",

year = "2015",

month = mar,

day = "9",

doi = "10.1016/j.tcs.2014.12.025",

language = "English",

volume = "570",

pages = "70--101",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "C",

}

TY - JOUR

T1 - Associative and commutative tree representations for Boolean functions

AU - Genitrini, Antoine

AU - Gittenberger, Bernhard

AU - Kraus, Veronika

AU - Mailler, Cécile

PY - 2015/3/9

Y1 - 2015/3/9

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

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

KW - Analytic combinatorics

KW - Asymptotic ratio

KW - Boolean functions

KW - Probability distribution

KW - Random boolean formulas

KW - Random trees

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

U2 - 10.1016/j.tcs.2014.12.025

DO - 10.1016/j.tcs.2014.12.025

M3 - Article

AN - SCOPUS:84926365296

SN - 0304-3975

VL - 570

SP - 70

EP - 101

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

Associative and commutative tree representations for Boolean functions

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this