On the minimal teaching sets of two-dimensional threshold functions

DOI10.1137/140978090MaRDI QIDQ3453571zbMATH OpenOpenAlexDBLPWikidataFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

arrangement of linesinteger latticeteaching setthreshold function

Mathematics Subject Classification ID

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) Computational learning theory (68Q32)

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)

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

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)