On the number of two-dimensional threshold functions

DOI10.1137/090750184MaRDI QIDQ3013151zbMATH OpenOpenAlexWikidataFDO

Authors Max A. Alekseyev

Publication date 18 July 2011

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0602511

zbMATH Keywords

Boolean functioninteger latticethreshold functionteaching setsquare lattice

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Many-valued logic (03B50) Asymptotic enumeration (05A16) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05)

Abstract: A two-dimensional threshold function of k-valued logic can be viewed as coloring of the points of a k x k square lattice into two colors such that there exists a straight line separating points of different colors. For the number of such functions only asymptotic bounds are known. We give an exact formula for the number of two-dimensional threshold functions and derive more accurate asymptotics.

Recommendations

• Asymptotics of the number of 2-threshold functions
• Note on the number of two-dimensional threshold functions
• Asymptotics of the number of threshold functions on a two-dimensional rectangular grid
• On the asymptotics of the logarithm of the number of threshold functions in K-valued logic
• On the number of threshold functions

Cited in

(11)

• Arrangements of hyperplanes and the number of threshold functions
• On teaching sets for 2-threshold functions of two variables
• Asymptotics for numbers of line segments and lines in a square grid
• Graphical enumeration and stained glass windows. I: Rectangular grids
• On a generalization of Tupper's formula for \(m\) colors and \(n\) dimensions
• Asymptotics of the number of 2-threshold functions
• Asymptotics of the number of threshold functions on a two-dimensional rectangular grid
• scientific article; zbMATH DE number 3869232 (Why is no real title available?)
• Note on the number of two-dimensional threshold functions
• The computing capacity of three-input multiple-valued one-threshold perceptrons
• On the minimal teaching sets of two-dimensional threshold functions

This page was built for publication: On the number of two-dimensional threshold functions

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