Complexity and Limiting Ratio of Boolean Functions over Implication

DOI10.1007/978-3-540-85238-4_28zbMath1173.03301OpenAlexW1850813354MaRDI QIDQ3599140

Daniéle Gardy, Bernhard Gittenberger, Antoine Genitrini, Hervé Fournier

Publication date: 3 February 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-85238-4_28

zbMATH Keywords

complexityprobability distributionBoolean functionsanalytic combinatoricsimplicational formulaslimiting ratio

Mathematics Subject Classification ID

Combinatorial probability (60C05) Boolean functions (06E30) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (1)

Associative and commutative tree representations for Boolean functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Using amplification to compute majority with small majority gates
• Random Boolean formulas representing any Boolean function with asymptotically equal probability
• Finite range random walk on free groups and homogeneous trees
• A natural prior probability distribution derived from the propositional calculus
• Statistics of intuitionistic versus classical logics
• Short monotone formulae for the majority function
• Classical and Intuitionistic Logic Are Asymptotically Identical
• On the density of truth of implicational parts of intuitionistic and classical logics
• Some typical properties of large AND/OR Boolean formulas
• Coloring rules for finite trees, and probabilities of monadic second order sentences
• Statistical properties of simple types
• And/Or Trees Revisited
• Statistics of implicational logic
• On asymptotic divergency in equivalential logics
• The Boolean functions computed by random Boolean formulas or how to grow the right function

This page was built for publication: Complexity and Limiting Ratio of Boolean Functions over Implication