The number of Boolean functions computed by formulas of a given size

DOI10.1002/(SICI)1098-2418(199810/12)13:3/4%3C349::AID-RSA9%3E3.0.CO;2-VMaRDI QIDQ4705331zbMATH OpenOpenAlexFDO

Authors Petr Savický, Alan R. Woods

Publication date 19 December 1999

Full work available at URL https://doi.org/10.1002/(sici)1098-2418(199810/12)13:3/4%3C349::aid-rsa9%3E3.0.co;2-v

zbMATH Keywords

Boolean functions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Boolean functions (06E30)

Recommendations

• Complexity and Probability of Some Boolean Formulas
• How Do Read-Once Formulae Shrink?
• Upper bounds for the formula size of symmetric Boolean functions
• scientific article; zbMATH DE number 3916176

Cited in

(8)

• Nearly optimal hierarchies for network and formula size
• On lengths of edge-labeled graph expressions
• Formulas versus Circuits for Small Distance Connectivity
• Using relevance queries for identification of read-once functions
• scientific article; zbMATH DE number 5370539 (Why is no real title available?)
• Almost-natural proofs
• Decomposition methods for generating algebraic expressions of full square rhomboids and other graphs
• Enumerating lambda terms by weighted length of their de Bruijn representation

This page was built for publication: The number of Boolean functions computed by formulas of a given size

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