A characterization of 2-threshold functions via pairs of prime segments

被引：1
作者：
Zamaraeva, Elena [1 ]
Zunic, Jovisa [2 ]
机构：
[1] Lobachevsky State Univ Nizhni Novgorod, Math Ctr, Nizhnii Novgorod, Russia
[2] Serbian Acad Sci, Math Inst, Belgrade, Serbia
来源：
THEORETICAL COMPUTER SCIENCE | 2022年 / 919卷
关键词：
Threshold function; k-Threshold function; Intersection of halfplanes; Integer lattice; Rectangular grid; Essential point; THRESHOLD FUNCTIONS; POLYHEDRAL SEPARABILITY; LEARNING INTERSECTIONS; BOOLEAN FUNCTIONS; TEACHING SETS; LOWER BOUNDS; NUMBER; ALGORITHMS; COMPLEXITY;
D O I：
10.1016/j.tcs.2022.03.025
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A {0, 1}-valued function on a two-dimensional rectangular grid is called threshold if its sets of zeros and ones are separable by a straight line. In this paper we study 2-threshold functions, i.e. functions representable as the conjunction of two threshold functions. We provide a characterization of 2-threshold functions by pairs of oriented prime segments, where each such segment is defined by an ordered pair of adjacent integer points. (C) 2022 Elsevier B.V. All rights reserved.
引用
收藏
页码：1 / 17
页数：17
相关论文
共 40 条
1234