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-VzbMATH Open0959.68525OpenAlexW1995952087MaRDI QIDQ4705331FDOQ4705331

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

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

zbMATH Keywords

Boolean functions

Mathematics Subject Classification ID

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

Cited In (8)

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

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)