Some typical properties of large AND/OR Boolean formulas

DOI10.1002/(SICI)1098-2418(199705)10:3%3C337::AID-RSA4%3E3.0.CO;2-XMaRDI QIDQ4344226zbMATH OpenOpenAlexFDO

Authors Hanno Lefmann, Petr Savický

Publication date 2 November 1997

Full work available at URL https://doi.org/10.1002/(sici)1098-2418(199705)10:3%3C337::aid-rsa4%3E3.0.co;2-x

zbMATH Keywords

binary trees chosen from the uniform distributionBoolean functionsize complexity

Mathematics Subject Classification ID

Boolean functions (06E30) Combinatorial probability (60C05) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Some typical properties of large AND/OR Boolean formulas
• Complexity and Probability of Some Boolean Formulas
• And/Or Trees Revisited
• And/or tree probabilities of Boolean functions
• The fraction of large random trees representing a given Boolean function in implicational logic

Cited in

(19)

• Enumerating lambda terms by weighted length of their de Bruijn representation
• Associative and commutative tree representations for Boolean functions
• The fraction of large random trees representing a given Boolean function in implicational logic
• Asymptotic properties of combinatory logic
• The distribution of height and diameter in random non-plane binary trees
• A sprouting tree model for random boolean functions
• Intuitionistic vs. Classical Tautologies, Quantitative Comparison
• Some typical properties of large AND/OR Boolean formulas
• Tautologies over implication with negative literals
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Complexity and Probability of Some Boolean Formulas
• Improved boolean formulas for the Ramsey graphs
• Moments of weights of random nonuniform Boolean functions
• Balanced and/or trees and linear threshold functions
• And/or tree probabilities of Boolean functions
• What is the satisfiability threshold of random balanced Boolean expressions?
• Fuzzy logics – quantitatively
• 2-Xor revisited: satisfiability and probabilities of functions
• Generalised and quotient models for random and/or~trees and application to satisfiability

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 Q4344226)