Associative and commutative tree representations for Boolean functions

DOI10.1016/j.tcs.2014.12.025zbMath1314.94120arXiv1305.0651OpenAlexW2155333593MaRDI QIDQ2514128

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

Publication date: 30 January 2015

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1305.0651

zbMATH Keywords

probability distributionBoolean functionsrandom treesanalytic combinatoricsrandom Boolean formulasasymptotic ratio

Mathematics Subject Classification ID

Related Items (4)

The effects of semantic simplifications on random \textit{BST}-like expression-trees ⋮ 2-Xor revisited: satisfiability and probabilities of functions ⋮ Generalised and quotient models for random and/or~trees and application to satisfiability ⋮ Numerical Algorithm for Pólya Enumeration Theorem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Probabilities of Boolean functions given by random implicational formulas
• Using amplification to compute majority with small majority gates
• A natural prior probability distribution derived from the propositional calculus
• Monotone Boolean formulas can approximate monotone linear threshold functions
• The fraction of large random trees representing a given Boolean function in implicational logic
• Short monotone formulae for the majority function
• Isomorphism and Symmetries in Random Phylogenetic Trees
• Singularity Analysis of Generating Functions
• Random Trees
• Complexity and Limiting Ratio of Boolean Functions over Implication
• Classical and Intuitionistic Logic Are Asymptotically Identical
• Amplification by Read-Once Formulas
• Some typical properties of large AND/OR Boolean formulas
• Statistical properties of simple types
• And/Or Trees Revisited
• Balanced And/Or trees and linear threshold functions
• The growing tree distribution on Boolean functions.
• The Boolean functions computed by random Boolean formulas or how to grow the right function

This page was built for publication: Associative and commutative tree representations for Boolean functions