Abstract
Interval functions constitute quite a special class of Boolean functions for which it is very easy and fast to determine their functional value on a specified input vector. The value of an n-variable interval function specified by interval [a, b] (where a and b are n-bit binary numbers) is true if and only if the input vector viewed as an n-bit number belongs to the interval [a, b].
Partially defined Boolean function (pdBf) is a pair (T, F) of sets of vectors representing truepoints and falsepoints respectively. In this paper we study the problem of finding an interval extension of given pdBf, that is a Boolean function f which respects truepoints and falsepoints of the input pdBf and can be represented by an interval.
We present a polynomial-time algorithm which solves this problem.