Publication at Faculty of Mathematics and Physics |
2007
Abstract
Boolean function f on n variables is represented by set I of disjoint intervals of non-negative n-bit integers, if the following condition holds: vector x of length n is a truepoint of f, if and only if integer m, binary representation of which corresponds to vector x, belongs to some interval from I. In this paper we present a polynomial-time algorithm recognizing, whether a Boolean function given by a positive prime DNF can be represented by two intervals.