Random Boolean expressions

MaRDI QIDQ3575996zbMATH OpenFDO

Authors Danièle Gardy

Publication date 28 July 2010

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/proceedings/article/view/dmAF0101/0.html

zbMATH Keywords

Boolean functioncomplexityprobability distribution for Boolean functionsprobability of tautologies

Mathematics Subject Classification ID

Classical propositional logic (03B05) Boolean functions (06E30) Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Recommendations

• 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
• A sprouting tree model for random boolean functions
• The fraction of large random trees representing a given Boolean function in implicational logic

Cited in

(23)

• Analysis of an efficient reduction algorithm for random regular expressions based on universality detection
• 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
• 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 4209213 (Why is no real title available?)
• Intuitionistic vs. Classical Tautologies, Quantitative Comparison
• Uniform approximation of continuous functions by probability functions of the Boolean bases
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Generation of mutants for boolean expression
• In the full propositional logic, 5/8 of classical tautologies are intuitionistically valid
• Complexity and Probability of Some Boolean Formulas
• Criterion of generativeness of sets of rational probabilities by a class of Boolean functions
• On the Degeneracy of Random Expressions Specified by Systems of Combinatorial Equations
• Analysis of Boolean variables using formal probability
• Uniform random expressions lack expressivity
• The relation between tree size complexity and probability for Boolean functions generated by uniform random trees
• Stochastic Algorithms: Foundations and Applications
• Fuzzy logics – quantitatively
• Simplifications of Uniform Expressions Specified by Systems
• A formal study of Boolean games with random formulas as payoff functions
• Asymptotic densities in logic and type theory

This page was built for publication: Random Boolean expressions

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