THE RELATION BETWEEN TREE SIZE COMPLEXITY AND PROBABILITY FOR BOOLEAN FUNCTIONS GENERATED BY UNIFORM RANDOM TREES - Université Pierre et Marie Curie Accéder directement au contenu
Article Dans Une Revue Applicable Analysis and Discrete Mathematics Année : 2016

THE RELATION BETWEEN TREE SIZE COMPLEXITY AND PROBABILITY FOR BOOLEAN FUNCTIONS GENERATED BY UNIFORM RANDOM TREES

Veronika Daxner
  • Fonction : Auteur
Antoine Genitrini
  • Fonction : Auteur
  • PersonId : 881263
Cecile Mailler

Résumé

An associative Boolean tree is a plane rooted tree whose internal nodes are labelled by and or or and whose leaves are labelled by literals taken from a fixed set of variables and their negations. We study the distribution induced on the set of Boolean functions by the uniform distribution on the set of associative trees of a large fixed size, where the size of a tree is defined as the number of its nodes. Using analytic combinatorics, we prove a relation between the probability of a given function and its tree size complexity.

Dates et versions

hal-01476145 , version 1 (24-02-2017)

Identifiants

Citer

Veronika Daxner, Antoine Genitrini, Bernhard Gittenberger, Cecile Mailler. THE RELATION BETWEEN TREE SIZE COMPLEXITY AND PROBABILITY FOR BOOLEAN FUNCTIONS GENERATED BY UNIFORM RANDOM TREES. Applicable Analysis and Discrete Mathematics, 2016, 10 (2), pp.408-446. ⟨10.2298/AADM160715015D⟩. ⟨hal-01476145⟩
173 Consultations
0 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More