Recognition of positive k-interval functions

David Kronus

Abstract:

Intervals [a_1,b_1],...,[a_k,b_k] of n-bit integers represent

Boolean function f on n variables if these intervals span just the

integers having as their binary representation some truepoint of f. The

correspondence of integers and Boolean vectors and hence also the

interval representation depends on the order which determines significancies of

individual bits. We consider the problem of recognizing whether a given

positive Boolean function can be represented by a specified number of

intervals with respect to a suitable order of bits. We present

algorithms for threshold and regular functions, an asymptotically

optimal algorithm recognizing whether a function given by a positive DNF can be

represented by 2 intervals and some ideas about the possibilities of

generalizing this algorithm for any number of intervals.