The fraction of large random trees representing a given Boolean function in implicational logic

DOI10.1002/rsa.20379zbMath1239.03004OpenAlexW2099426885MaRDI QIDQ2884007

Daniéle Gardy, Bernhard Gittenberger, Antoine Genitrini, Hervé Fournier

Publication date: 14 May 2012

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

Full work available at URL: https://doi.org/10.1002/rsa.20379

zbMATH Keywords

complexitybranching processesprobability distributionBoolean functionsanalytic combinatoricsread-once functionsimplicational formulaslimiting ratio

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Boolean functions (06E30) Logical aspects of Boolean algebras (03G05) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (5)

Enumerating lambda terms by weighted length of their de Bruijn representation ⋮ On the number of unary-binary tree-like structures with restrictions on the unary height ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Associative and commutative tree representations for Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using amplification to compute majority with small majority gates
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• Finite range random walk on free groups and homogeneous trees
• A natural prior probability distribution derived from the propositional calculus
• Statistics of intuitionistic versus classical logics
• Short monotone formulae for the majority function
• Tautologies over implication with negative literals
• Classical and Intuitionistic Logic Are Asymptotically Identical
• On the density of truth of implicational parts of intuitionistic and classical logics
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• 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
• Statistics of implicational logic
• On asymptotic divergency in equivalential logics
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• On sentences which are true of direct unions of algebras
• Logic for computer scientists

This page was built for publication: The fraction of large random trees representing a given Boolean function in implicational logic