Relations between threshold and k‐interval Boolean functions

Relations between threshold and k‐interval Boolean functions

0.00 Avg rating0 Votes
Article ID: iaor20117926
Volume: 188
Issue: 1
Start Page Number: 263
End Page Number: 278
Publication Date: Aug 2011
Journal: Annals of Operations Research
Authors:
Keywords: boolean programming
Abstract:

Every k‐interval Boolean function f can be represented by at most k intervals of integers such that vector x is a truepoint of f if and only if the integer represented by x belongs to one of these k (disjoint) intervals. Since the correspondence of Boolean vectors and integers depends on the order of bits an interval representation is also specified with respect to an order of variables of the represented function. Interval representation can be useful as an efficient representation for special classes of Boolean functions which can be represented by a small number of intervals. In this paper we study inclusion relations between the classes of threshold and k‐interval Boolean functions. We show that positive 2‐interval functions constitute a (proper) subclass of positive threshold functions and that such inclusion does not hold for any k>2. We also prove that threshold functions do not constitute a subclass of k‐interval functions, for any k.

Reviews

Required fields are marked *. Your email address will not be published.