Skip to Main content Skip to Navigation

# And/or tree probabilities of Boolean functions

Abstract : We consider two probability distributions on Boolean functions defined in terms of their representations by $\texttt{and/or}$ trees (or formulas). The relationships between them, and connections with the complexity of the function, are studied. New and improved bounds on these probabilities are given for a wide class of functions, with special attention being paid to the constant function $\textit{True}$ and read-once functions in a fixed number of variables.
Keywords :
Document type :
Conference papers
Domain :
Complete list of metadata

Cited literature [11 references]

https://hal.inria.fr/hal-01184027
Contributor : Coordination Episciences Iam <>
Submitted on : Wednesday, August 12, 2015 - 3:51:30 PM
Last modification on : Friday, January 10, 2020 - 3:42:21 PM
Long-term archiving on: : Friday, November 13, 2015 - 11:39:58 AM

### File

dmAD0113.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01184027, version 1

### Citation

Danièle Gardy, Alan Woods. And/or tree probabilities of Boolean functions. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.139-146. ⟨hal-01184027⟩

Record views

Files downloads