Publication at Faculty of Mathematics and Physics |
2007
Abstract
Interval functions constitute 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].
Renamable interval functions can be transformed into interval functions by switching the polarity of some variables. In this paper we study the problem of finding a renamable interval extension of given partially defined Boolean function.
We present a polynomial-time algorithm which solves this problem.