And-or tree probabilities of Boolean functions - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

1 PRISM - Parallélisme, Réseaux, Systèmes, Modélisation 2 School of Mathematics and Statistics Crawley, Perth

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 : Boolean formula And-Or tree tree enumeration tautology





Autor: Danièle Gardy - Alan Woods -

Fuente: https://hal.archives-ouvertes.fr/

Enviar