On the minimal teaching sets of two-dimensional threshold functions

DOI10.1137/140978090MaRDI QIDQ3453571zbMATHOpenAlexDBLPWikidataFDO

Authors Marina G. Basova, Max A. Alekseyev, N. Yu. Zolotykh

Publication date 27 November 2015

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

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

zbMATH Keywords

integer latticethreshold functionarrangement of linesteaching set

Mathematics Subject Classification ID

Computational learning theory (68Q32) Exact enumeration problems, generating functions (05A15) Partitions of sets (05A18) Combinatorial aspects of matroids and geometric lattices (05B35) Lattices and convex bodies in (2) dimensions (aspects of discrete geometry) (52C05) Planar arrangements of lines and pseudolines (aspects of discrete geometry) (52C30)

Abstract: It is known that a minimal teaching set of any threshold function on the twodimensional rectangular grid consists of 3 or 4 points. We derive exact formulae for the numbers of functions corresponding to these values and further refine them in the case of a minimal teaching set of size 3. We also prove that the average cardinality of the minimal teaching sets of threshold functions is asymptotically 7/2. We further present corollaries of these results concerning some special arrangements of lines in the plane.

Recommendations

• On teaching sets for 2-threshold functions of two variables
• On teaching sets of k-threshold functions
• On an upper bound for the cardinality of a minimal teaching set of a threshold function
• On the number of two-dimensional threshold functions
• Asymptotics of the number of 2-threshold functions

Cited in

(8)

• A characterization of 2-threshold functions via pairs of prime segments
• On teaching sets of \(k\)-threshold functions
• On an upper bound for the cardinality of a minimal teaching set of a threshold function
• Asymptotics of the number of 2-threshold functions
• On Boolean threshold functions with minimum specification number
• On teaching sets for 2-threshold functions of two variables
• Graphical enumeration and stained glass windows. I: Rectangular grids
• On the number of irreducible points in polyhedra

This page was built for publication: On the minimal teaching sets of two-dimensional threshold functions

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