*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.