Some typical properties of large AND/OR Boolean formulas

DOI10.1007/3-540-60246-1_130MaRDI QIDQ3569015zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(7)

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

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)