A sprouting tree model for random boolean functions

DOI10.1002/RSA.20567MaRDI QIDQ3460511zbMATH OpenOpenAlexFDO

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

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

binary search tree model of growthbinary treesBoolean expressionsBoolean formulasBoolean functionsYule tree

Mathematics Subject Classification ID

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

Recommendations

• The growing tree distribution on Boolean functions.
• Randomized Boolean decision trees: Several remarks
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
• And/or tree probabilities of Boolean functions
• The fraction of large random trees representing a given Boolean function in implicational logic
• A generalized distribution model for random recursive trees
• Random trees and applications
• On growing random binary trees
• scientific article; zbMATH DE number 1444332
• Generalised and quotient models for random and/or~trees and application to satisfiability

Cites work

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

Cited in

(9)

• Pseudorandom binary functions on rooted plane trees
• Random Boolean expressions
• Uniform random expressions lack expressivity
• The growing tree distribution on Boolean functions.
• Pseudorandom binary functions on Bratteli diagrams
• Exploring the average values of Boolean functions via asymptotics and experimentation
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
• What is the satisfiability threshold of random balanced Boolean expressions?
• Generalised and quotient models for random and/or~trees and application to satisfiability

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460511)