The Library
Combinatorial and learning properties of threshold and related functions
Tools
Zamaraeva, Elena (2020) Combinatorial and learning properties of threshold and related functions. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Zamaraeva_2020.pdf - Submitted Version - Requires a PDF viewer. Download (882Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3685527~S15
Abstract
This thesis is devoted to the study of threshold and related functions over two different domains.
In the first part, we consider Boolean threshold and linear read-once functions. We show that a positive function f of n variables has exactly n + 1 extremal points if and only if it is linear read-once. The class of linear read-once functions is also known to be the intersection of the classes of read-once and threshold functions. Generalizing this result we show that the class of linear read-once functions is the intersection of read-once and Chow functions. Then, we characterize the class of linear read-once functions by means of minimal forbidden subfunctions within the universe of read-once and the universe of threshold functions. Furthermore, we prove that the subclass of threshold functions with the minimum specification number does not coincide with the class of linear read-once functions thereby disproving a conjecture of Anthony et al. from 1995 [6]. We propose techniques that we believe might be useful to characterize the subclass of threshold functions with the minimum specification number. We also found all threshold functions up to 6 variables
from this subclass.
In the second part, we turn to the k-threshold functions over a two-dimensional rectangular grid, i.e. the functions representable as the conjunctions of k threshold functions. In [34] a bijection between non-constant threshold functions over this domain and prime segments was established. This result was used in [34] to estimate the number of threshold functions asymptotically. No asymptotic formula for the number of k-threshold functions was known for k > 1. We consider the case k = 2 and characterize 2-threshold functions via the pairs of oriented prime segments with specific properties. We apply this characterization to derive an asymptotic formula for the number of 2-threshold functions depending on the size of the grid. This result also improves a trivial upper bound on the number of k-threshold functions for k > 2.
In the third part, we study specifying sets of k-threshold functions. First, we consider the class of k-threshold functions with non-fixed k, i.e. the union of all k-threshold functions for all k. We prove that a function in this class has a unique minimal specifying set with respect to the class of k threshold functions with non-fixed k and provide the structural characterization of this set. For two-dimensional k-threshold functions we refine the given structure and derive a bound on the size of the minimal specifying set. Then we fix the parameter k = 2 and analyze the size and the number of minimal specifying sets of two-dimensional 2-threshold functions. In particular, we construct a sequence of 2-threshold functions over a squared grid of size m _ m for which the number of minimal specifying sets grows as _(m2). We also show that if a two-dimensional 2-threshold function has a unique representation as a conjunction of two threshold functions, then its specification number is at most 9. The results of this part of the thesis were obtained prior to the Ph.D. study and are therefore provided as a supplementary material.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Threshold logic, Combinatorial analysis, Algebra, Boolean | ||||
Official Date: | September 2020 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Lozin, Vadim ; Zolotykh, Nikolai | ||||
Extent: | vi, 119 leaves | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year