Characterization of Multiple-Valued Threshold Functions in the Vilenkin-Chrestenson Basis

摘要

A multiple-valued threshold function is a discrete function which induces a partition of its domain set into (non-empty) subsets, where the subsets are separable with parallel hyperplanes. If the number of subsets is not greater than k, the function is called a k-level threshold. In this paper, we propose a characterization of threshold functions using the Vilenkin-Chrestenson transformation. The main result of the paper shows that a 2-level threshold function is uniquely characterized by only the partial spectrum of the function. We also provide a characterization of general k-level threshold functions using the additional zero-order spectral coefficients of a suitably chosen characters of the function.The initial results of this paper were presented at the conference ISMVL 2018, and published in [13].