Publication at Faculty of Mathematics and Physics |
2007
Abstract
This thesis is dedicated to a research concerning representations of Boolean functions. We present the concept of a representation using intervals of integers.
We define classes of functions which can be represented by a small number of such interval and study their properties. We study the problem of recognizing whether a given function can be represented by a given number of intervals and the problem of deciding whether a given partial function can be extended to a total function which can be represented by a small number of intervals.
We show polynomial algorithms for some variants of these problems and prove NP-hardness for other.