On the number of two-dimensional threshold functions

DOI10.1137/090750184zbMATH Open1231.94092arXivmath/0602511OpenAlexW3102910158WikidataQ57056997 ScholiaQ57056997MaRDI QIDQ3013151FDOQ3013151

Authors: Max A. Alekseyev 

Publication date: 18 July 2011

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

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.

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

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

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)

Cited In (5)

• Arrangements of hyperplanes and the number of threshold functions
• Asymptotics for numbers of line segments and lines in a square grid
• Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids
• Title not available (Why is that?)
• The computing capacity of three-input multiple-valued one-threshold perceptrons

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)