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

DOI10.1002/RSA.20379MaRDI QIDQ2884007zbMATH OpenOpenAlexFDO

Authors Danièle Gardy, Antoine Genitrini, Bernhard Gittenberger, 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 distributionread-once functionsBoolean functionsanalytic combinatoricsimplicational formulaslimiting ratio

Mathematics Subject Classification ID

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

Recommendations

• Complexity and Limiting Ratio of Boolean Functions over Implication
• Probabilities of Boolean functions given by random implicational formulas
• Random Boolean expressions
• Some typical properties of large AND/OR Boolean formulas
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees

Cites work

• A natural prior probability distribution derived from the propositional calculus
• And/Or Trees Revisited
• Asymptotic density for equivalence
• Boltzmann oracle for combinatorial systems
• Classical and Intuitionistic Logic Are Asymptotically Identical
• Coloring rules for finite trees, and probabilities of monadic second order sentences
• Density of truth in modal logics
• Finite range random walk on free groups and homogeneous trees
• Linear-time algorithms for testing the satisfiability of propositional horn formulae
• Logic for computer scientists
• On asymptotic divergency in equivalential logics
• On sentences which are true of direct unions of algebras
• On the asymptotic density of tautologies in logic of implication and negation
• On the density of truth of implicational parts of intuitionistic and classical logics
• Random Boolean expressions
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• Short monotone formulae for the majority function
• Some typical properties of large AND/OR Boolean formulas
• Statistical properties of simple types
• Statistics of implicational logic
• Statistics of intuitionistic versus classical logics
• Tautologies over implication with negative literals
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• Using amplification to compute majority with small majority gates

Cited in

(10)

• Probabilities of Boolean functions given by random implicational formulas
• 2-Xor revisited: satisfiability and probabilities of functions
• Generalised and quotient models for random and/or~trees and application to satisfiability
• Random Boolean expressions
• Statistics of implicational logic
• Associative and commutative tree representations for Boolean functions
• 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
• Complexity and Limiting Ratio of Boolean Functions over Implication
• A sprouting tree model for random boolean functions

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

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