Probabilities of Boolean functions given by random implicational formulas

MaRDI QIDQ426921zbMATHFDO

Authors Antoine Genitrini, Bernhard Gittenberger, Veronika Kraus, Cécile Mailler

Publication date 12 June 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL http://www.emis.de/journals/EJC/ojs/index.php/eljc/article/view/v19i2p37

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

complexityBoolean functionsanalytic combinatoricsBoolean formulasimplicational fragmentrandom Boolean expressionsShannon effect

Mathematics Subject Classification ID

Combinatorial probability (60C05) Classical propositional logic (03B05) Asymptotic enumeration (05A16) Boolean functions (06E30)

Recommendations

• The fraction of large random trees representing a given Boolean function in implicational logic
• Complexity and Limiting Ratio of Boolean Functions over Implication
• No Shannon effect on probability distributions on Boolean functions induced by random expressions
• Complexity and Probability of Some Boolean Formulas
• Asymptotic probability of values of random Boolean expressions

Cited in

(17)

• No Shannon effect on probability distributions on Boolean functions induced by random expressions
• scientific article; zbMATH DE number 3893093 (Why is no real title available?)
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• A combinatorial method for the evaluation of probabilities of complex Boolean functions
• Probabilistic Aspects of Boolean Switching Functions via a New Transform
• Formulas for approximating pseudo-Boolean random variables
• Stochastic Algorithms: Foundations and Applications
• Probabilities of 2-Xor Functions
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Associative and commutative tree representations for Boolean functions
• 2-Xor revisited: satisfiability and probabilities of functions
• scientific article; zbMATH DE number 3863116 (Why is no real title available?)
• Asymptotic probability of values of random Boolean expressions
• The fraction of large random trees representing a given Boolean function in implicational logic
• Oblivious bounds on the probability of boolean functions
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• Enumerating lambda terms by weighted length of their de Bruijn representation

This page was built for publication: Probabilities of Boolean functions given by random implicational formulas

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