On the Properties of Asymptotic Probability for Random Boolean Expression Values in Binary Bases
- 595 Downloads
The present paper deals with the problem of analyzing the value of a random Boolean expression. The expressions are constructed of Boolean operations and constants chosen independently at random with given probabilities. The dependence between the expression value probability and the constants’ probabilities is investigated for different sets of operations. The asymptotic behavior of this dependence is given by a probability function, explicitly obtained through analysis of generating functions for expressions. Special attention is given to the case of binary Boolean operations.
The paper demonstrates some probability function properties and their connection with the properties of Boolean operations used in random expressions.
Unable to display preview. Download preview PDF.
- 1.Flajolet, P., Sedgewick, R.: Analytic Combinatorics: Functional Equations, Rational and Algebraic Functions. Research Report 4103, INRIA (2001)Google Scholar