The fraction of large random trees representing a given Boolean function in implicational logic
DOI10.1002/RSA.20379zbMATH Open1239.03004OpenAlexW2099426885MaRDI QIDQ2884007FDOQ2884007
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
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
complexitybranching processesprobability distributionread-once functionsBoolean functionsanalytic combinatoricsimplicational formulaslimiting ratio
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)
Cites Work
- Short monotone formulae for the majority function
- On sentences which are true of direct unions of algebras
- Finite range random walk on free groups and homogeneous trees
- Classical and Intuitionistic Logic Are Asymptotically Identical
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Coloring rules for finite trees, and probabilities of monadic second order sentences
- Statistical properties of simple types
- Random Boolean expressions
- And/Or Trees Revisited
- Boltzmann oracle for combinatorial systems
- Using amplification to compute majority with small majority gates
- A natural prior probability distribution derived from the propositional calculus
- Some typical properties of large AND/OR Boolean formulas
- On the asymptotic density of tautologies in logic of implication and negation
- The Boolean functions computed by random Boolean formulas or how to grow the right function
- On asymptotic divergency in equivalential logics
- Random Boolean formulas representing any Boolean function with asymptotically equal probability
- Statistics of intuitionistic versus classical logics
- Density of truth in modal logics
- On the density of truth of implicational parts of intuitionistic and classical logics
- Tautologies over implication with negative literals
- Statistics of implicational logic
- Asymptotic density for equivalence
- Logic for computer scientists
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)
