The threshold order of a Boolean function

DOI10.1016/0166-218X(91)90032-RMaRDI QIDQ805595zbMATH OpenFDO

Authors Chi Wang, Alton C. Williams

Publication date 1991

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(91)90032-R

zbMATH Keywords

Boolean functionNP-complete problemthreshold functions

Mathematics Subject Classification ID

Review text

This paper contains the following results: characterization of threshold functions of order n; the problem of recognizing whether a Boolean function is a threshold function of order m is an NP-complete problem; a characterization of threshold functions in terms of summability; the number of threshold functions for dimension \(n\leq 7\).

Recommendations

• scientific article; zbMATH DE number 850396
• scientific article; zbMATH DE number 822063
• A threshold property of quadratic Boolean functions
• Threshold Boolean logic
• On Boolean threshold functions with minimum specification number
• Realization of boolean functions using threshold elements
• Relations between threshold and \(k\)-interval Boolean functions
• Boolean Functions Satisfying Higher Order Propagation Criteria
• scientific article; zbMATH DE number 1346056
• On the functional separability of Boolean threshold functions

Cites work

• An Algorithm to Dualize a Regular Switching Function
• Dualization of regular Boolean functions
• Enumeration of Threshold Functions of Eight Variables
• scientific article; zbMATH DE number 3598234 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3249560 (Why is no real title available?)
• scientific article; zbMATH DE number 3329024 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• On defining sets of vertices of the hypercube by linear inequalities
• Polynomial-time algorithms for regular set-covering and threshold synthesis
• The threshold order of a Boolean function

Cited in

(24)

• Equivalence of operations with respect to discriminator clones
• Order of state functions and logic functions
• Addendum to: The threshold order of a Boolean function
• Trading properties and Alexandrov kernels for Boolean functions
• Definability of Boolean function classes by linear equations over \(\mathbf{GF}(2)\)
• Boolean minors
• Classification by polynomial surfaces
• On the geometric separability of Boolean functions
• On Boolean threshold functions with minimum specification number
• Trading transforms of non-weighted simple games and integer weights of weighted simple games
• Extremal properties of polynomial threshold functions
• Quadratization of symmetric pseudo-Boolean functions
• Joint realizability of monotone Boolean functions
• Threshold Boolean logic
• scientific article; zbMATH DE number 3902556 (Why is no real title available?)
• scientific article; zbMATH DE number 850396 (Why is no real title available?)
• Polynomial threshold functions, hyperplane arrangements, and random tensors
• Clones with finitely many relative \({\mathcal R}\)-classes
• On the constructive characterization of threshold functions
• On neuronal capacity
• Hadamard powers and kernel perceptrons
• Minors of Boolean functions with respect to clique functions and hypergraph homomorphisms
• The threshold order of a Boolean function
• Algebraic and topological closure conditions for classes of pseudo-Boolean functions

This page was built for publication: The threshold order of a Boolean function

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