The fraction of large random trees representing a given Boolean function in implicational logic
- 31 August 2011
- journal article
- research article
- Published by Wiley in Random Structures & Algorithms
- Vol. 40 (3) , 317-349
Abstract
No abstract availableKeywords
Funding Information
- FWF
- National Research Area (S9600 (S9604), ÖAD (F03/2010))
- A.N.R. projects SADA, BOOLE, P.H.C. Amadeus project Probabilities and tree representations for Boolean functions
This publication has 30 references indexed in Scilit:
- Tautologies over implication with negative literalsMathematical Logic Quarterly, 2010
- On asymptotic divergency in equivalential logicsMathematical Structures in Computer Science, 2008
- On the density of truth of implicational parts of intuitionistic and classical logicsJournal of Applied Non-Classical Logics, 2003
- Statistical properties of simple typesMathematical Structures in Computer Science, 2000
- Systems of functional equationsRandom Structures & Algorithms, 2000
- Coloring rules for finite trees, and probabilities of monadic second order sentencesRandom Structures & Algorithms, 1997
- Using amplification to compute majority with small majority gatescomputational complexity, 1996
- Finite Range Random Walk on Free Groups and Homogeneous TreesThe Annals of Probability, 1993
- Linear-time algorithms for testing the satisfiability of propositional horn formulaeThe Journal of Logic Programming, 1984
- Short monotone formulae for the majority functionJournal of Algorithms, 1984