Some typical properties of large AND/OR Boolean formulas

DOI10.1007/3-540-60246-1_130zbMATH Open1193.03018OpenAlexW1570924439MaRDI QIDQ3569015FDOQ3569015

Authors: Hanno Lefmann, Petr Savický 

Publication date: 17 June 2010

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-60246-1_130

Recommendations

• Some typical properties of large AND/OR Boolean formulas
• And/Or Trees Revisited
• And/or tree probabilities of Boolean functions
• Complexity and Probability of Some Boolean Formulas
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees

Mathematics Subject Classification ID

Trees (05C05) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Classical propositional logic (03B05)

Cited In (7)

• The Boolean functions computed by random Boolean formulas or how to grow the right function
• Generalised and quotient models for random and/or~trees and application to satisfiability
• Equivalence classes of random Boolean trees and application to the Catalan satisfiability problem
• Balanced and/or trees and linear threshold functions
• Improved boolean formulas for the Ramsey graphs
• The fraction of large random trees representing a given Boolean function in implicational logic
• And/or tree probabilities of Boolean functions

This page was built for publication: Some typical properties of large AND/OR Boolean formulas

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