Encoding of multilevel S-threshold functions

Abstract

We consider the encoding problem for the multilevel S-threshold functions. Multilevel S-threshold functions correspond to partitions of a finite-dimensional integer grid into a given finite number of levels, by parallel hypersurfaces. These hypersurfaces are representable as linear combinations of monomials from a predefined set S. We describe and analyze an encoding scheme applicable to all multilevel S-threshold functions, based on the use discrete moments. Even though the proposed encoding scheme is very general, there are situations where it outperforms the existing ones and, as a by product, gives a sharper upper bound for the number of certain threshold functions. Also, several existing encoding schemes, for particular classes of threshold functions, are special cases of this, very general, encoding scheme considered in this paper. Initial results of this paper were presented at the ISMVL 2014, and published in [17].