On the minimal teaching sets of two-dimensional threshold functions

DOI10.1137/140978090zbMATH Open1326.05006DBLPjournals/siamdm/AlekseyevBZ15arXiv1307.1058OpenAlexW3099996730WikidataQ57056927 ScholiaQ57056927MaRDI QIDQ3453571FDOQ3453571

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)

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.

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

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

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)

Cited In (8)

• A characterization of 2-threshold functions via pairs of prime segments
• On Boolean threshold functions with minimum specification number
• On teaching sets for 2-threshold functions of two variables
• On the number of irreducible points in polyhedra
• Asymptotics of the number of 2-threshold functions
• On teaching sets of \(k\)-threshold functions
• Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids
• On an upper bound for the cardinality of a minimal teaching set of a threshold function

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)