On the Properties of Asymptotic Probability for Random Boolean Expression Values in Binary Bases

  • Alexey D. Yashunsky
Conference paper
Part of the Lecture Notes in Computer Science book series (LNCS, volume 3777)


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.

Unable to display preview. Download preview PDF.


  1. 1.
    Flajolet, P., Sedgewick, R.: Analytic Combinatorics: Functional Equations, Rational and Algebraic Functions. Research Report 4103, INRIA (2001)Google Scholar
  2. 2.
    Savický, P.: Complexity and Probability of some Boolean Formulas. Combinatorics, Probability and Computing 7(4), 451–463 (1998)zbMATHCrossRefMathSciNetGoogle Scholar
  3. 3.
    Chauvin, B., Flajolet, P., Gardy, D., Gittenberger, B.: And/Or trees revisited. Combinatorics, Probability and Computing 13(4-5), 475–497 (2004)zbMATHCrossRefMathSciNetGoogle Scholar

Copyright information

© Springer-Verlag Berlin Heidelberg 2005

Authors and Affiliations

  • Alexey D. Yashunsky
    • 1
  1. 1.Department of Discrete Mathematics, Faculty of Mechanics and MathematicsMoscow State UniversityMoscowRussia

Personalised recommendations