Publications in Scientific Journals:
A. Genitrini, B. Gittenberger, V. Kraus, C. Mailler:
"Associative and commutative tree representations for Boolean functions";
Theoretical Computer Science,
570
(2015),
70
- 101.
English 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:
Boolean functions; Probability distribution; Random Boolean formulas; Random trees; Asymptotic ratio; Analytic combinatorics
"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)
http://dx.doi.org/10.1016/j.tcs.2014.12.025
Created from the Publication Database of the Vienna University of Technology.