HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# 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 :

Cited literature [11 references]

https://hal.inria.fr/hal-01184027
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 3:51:30 PM
Last modification on : Wednesday, October 20, 2021 - 12:24:14 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:39:58 AM

### File

Publisher files allowed on an open archive

### 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, ⟨10.46298/dmtcs.3355⟩. ⟨hal-01184027⟩

Record views