Probabilities of Boolean functions given by random implicational formulas

MaRDI QIDQ426921zbMATH OpenFDO

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

analytic combinatoricsBoolean formulasBoolean functionscomplexityimplicational fragmentrandom Boolean expressionsShannon effect

Mathematics Subject Classification ID

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

Review text

Summary: We study the asymptotic relation between the probability and the complexity of Boolean functions in the implicational fragment which are generated by large random Boolean expressions involving variables and implication, as the number of variables tends to infinity. In contrast to models studied in the literature so far, we consider two expressions to be equal if they differ only in the order of the premises. A precise asymptotic formula is derived for functions of low complexity. Furthermore, we show that this model does not exhibit the Shannon effect.

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)

• 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
• Oblivious bounds on the probability of boolean functions
• No Shannon effect on probability distributions on Boolean functions induced by random expressions
• Asymptotic probability of values of random Boolean expressions
• scientific article; zbMATH DE number 3863116 (Why is no real title available?)
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Probabilistic Aspects of Boolean Switching Functions via a New Transform
• scientific article; zbMATH DE number 3893093 (Why is no real title available?)
• Probabilities of 2-Xor Functions
• Stochastic Algorithms: Foundations and Applications
• The Boolean functions computed by random Boolean formulas or how to grow the right function
• A combinatorial method for the evaluation of probabilities of complex Boolean functions
• 2-Xor revisited: satisfiability and probabilities of functions
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• Formulas for approximating pseudo-Boolean random variables

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)