Minimální reprezentace víceintervalových booleovských funkcí

When we interpret the input vector of a Boolean function as a binary number, we define interval Boolean function fn [a,b] so that fn [a,b](x) = 1 if and only if a ≤ x ≤ b. Disjunctive normal form is a common way of representing Boolean functions. Minimization of DNF representation of an interval Boolean function can be per- formed in linear time. The natural generalization to k-interval functions seems to be significantly harder to tackle. In this thesis, we discuss the difficulties with finding an optimal solution and introduce a 2k-approximation algorithm