The generalized complexity of linear Boolean functions

DOI10.1515/DMA-2020-0004MaRDI QIDQ2295973zbMATH OpenOpenAlexFDO

Authors Nikolay P. Red'kin

Publication date 17 February 2020

Published in Discrete Mathematics and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1515/dma-2020-0004

zbMATH Keywords

Boolean circuitBoolean functioncomplexity of Boolean functionShannon function

Mathematics Subject Classification ID

Boolean functions (06E30) Switching theory, applications of Boolean algebras to circuits and networks (94C11) Boolean functions (94D10)

Recommendations

• Realization of linear functions by formulas in various bases
• On the complexity of realization of the linear function by formulas over finite Boolean bases
• The minimal circuits for linear Boolean functions
• Complexity of realization of a linear Boolean function in Sheffer's basis
• On minimal realizations of linear Boolean functions

Cites work

• A generalization of Shannon function
• Complexity of realization of a linear Boolean function in Sheffer's basis
• scientific article; zbMATH DE number 4172919 (Why is no real title available?)
• scientific article; zbMATH DE number 2095572 (Why is no real title available?)
• scientific article; zbMATH DE number 6460060 (Why is no real title available?)
• scientific article; zbMATH DE number 3358361 (Why is no real title available?)
• scientific article; zbMATH DE number 3422273 (Why is no real title available?)
• On minimal circuits for linear functions over some bases
• On minimal realizations of linear Boolean functions
• The minimal circuits for linear Boolean functions

Cited in

(22)

• General upper bound of circuit complexity in an arbitrary infinite complete base
• On the complexity of realizing the powers of a Boolean (n,n)-function
• Complexity of Boolean functions over bases with unbounded fan-in gates
• Realization of linear functions by formulas in various bases
• Sequential computation of linear Boolean mappings
• Formula complexity of a linear function in a \(k\)-ary basis
• Implementation complexity of Boolean functions with a small number of ones
• On the complexity of a cyclic shift of a set of real numbers
• On the comparison of complexity of two ways of realization of some linear Boolean functions
• Complexity of realization of a linear Boolean function in Sheffer's basis
• scientific article; zbMATH DE number 3981870 (Why is no real title available?)
• scientific article; zbMATH DE number 4027365 (Why is no real title available?)
• scientific article; zbMATH DE number 176868 (Why is no real title available?)
• scientific article; zbMATH DE number 1071791 (Why is no real title available?)
• On the complexity of realization of the linear function by formulas over finite Boolean bases
• Complexity of the realization of a linear Boolean function in the class of -schemes
• On minimal realizations of linear Boolean functions
• Complexity of Linear Boolean Operators
• Linear Transformations in Boolean Complexity Theory
• scientific article; zbMATH DE number 3328172 (Why is no real title available?)
• On the Delay Required to Realize Boolean Functions
• Lower bounds on the formula complexity of a linear Boolean function

This page was built for publication: The generalized complexity of linear Boolean functions

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