Authors: | Zamaraeva, Elena Žunić, Joviša |
Affiliations: | Mathematical Institute of the Serbian Academy of Sciences and Arts | Title: | A characterization of 2-threshold functions via pairs of prime segments | Journal: | Theoretical Computer Science | Volume: | 919 | First page: | 1 | Last page: | 17 | Issue Date: | 2022 | Rank: | M23 | ISSN: | 0304-3975 | DOI: | 10.1016/j.tcs.2022.03.025 | Abstract: | 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. |
Keywords: | Essential point | Integer lattice | Intersection of halfplanes | k-Threshold function | Rectangular grid | Threshold function | Publisher: | Elsevier |
Show full item record
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.