Publication at Faculty of Mathematics and Physics |
2016
Abstract
In this short note we will present a less common way how to represent a Boolean function, namely a representation by switch-list. There are two problems connected to such representation: (1) a knowledge compilation problem, i.e. a problem of transforming a given representation of a Boolean function (e.g. a DNF, CNF, BDD ...) into a switch-listl representation, and (2) a knowledge compression problem, i.e. a problem of finding the most compact switch-list representation among those which represent the same function.
We will summarize known results about these two problems and present a new one about the compilation problem.