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 readonce functions. We show that a positive function f of n variables has exactly n + 1 extremal points if and only if it is linear readonce. The class of linear readonce functions is also known to be the intersection of the classes of readonce and threshold functions. Generalizing this result we show that the class of linear readonce functions is the intersection of readonce and Chow functions. Then, we characterize the class of linear readonce functions by means of minimal forbidden subfunctions within the universe of readonce 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 readonce 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 kthreshold functions over a twodimensional rectangular grid, i.e. the functions representable as the conjunctions of k threshold functions. In [34] a bijection between nonconstant 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 kthreshold functions was known for k > 1. We consider the case k = 2 and characterize 2threshold functions via the pairs of oriented prime segments with specific properties. We apply this characterization to derive an asymptotic formula for the number of 2threshold functions depending on the size of the grid. This result also improves a trivial upper bound on the number of kthreshold functions for k > 2.
In the third part, we study specifying sets of kthreshold functions. First, we consider the class of kthreshold functions with nonfixed k, i.e. the union of all kthreshold 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 nonfixed k and provide the structural characterization of this set. For twodimensional kthreshold 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 twodimensional 2threshold functions. In particular, we construct a sequence of 2threshold 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 twodimensional 2threshold 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