A sprouting tree model for random boolean functions

DOI10.1002/rsa.20567zbMath1327.05302OpenAlexW2070710763MaRDI QIDQ3460511

Cécile Mailler, Daniéle Gardy, Brigitte Chauvin

Publication date: 7 January 2016

Published in: Random Structures & Algorithms (Search for Journal in Brave)

Full work available at URL: http://opus.bath.ac.uk/52305/1/ABR_version_longue.pdf

zbMATH Keywords

Boolean functionsBoolean expressionsbinary treesYule treeBoolean formulasbinary search tree model of growth

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Boolean functions (06E30)

Related Items (max. 100)

What is the satisfiability threshold of random balanced Boolean expressions? ⋮ Unnamed Item ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability

Cites Work

• Boolean function complexity. Advances and frontiers.
• Martingales and profile of binary search trees
• On growing random binary trees
• Finite range random walk on free groups and homogeneous trees
• A natural prior probability distribution derived from the propositional calculus
• Occupancy urn models in the analysis of algorithms
• Analytic urns
• Statistics of intuitionistic versus classical logics
• Monotone Boolean formulas can approximate monotone linear threshold functions
• Complexity Theory
• Singularity Analysis of Generating Functions
• Tautologies over implication with negative literals
• Some typical properties of large AND/OR Boolean formulas
• Coloring rules for finite trees, and probabilities of monadic second order sentences
• Statistical properties of simple types
• And/Or Trees Revisited

This page was built for publication: A sprouting tree model for random boolean functions