| Abstract: |
In this paper we focus on a slightly unusual way how to represent Boolean functions,
namely on representations by switch-lists. Given a truth table representation of a Boolean
function f the switch-list representation of $f$ is a list of Boolean vectors from the truth table
which have a different function value than the preceding Boolean vector in the truth table.
The main aim of our research is to describe a compilation algorithm from switch-lists to OBDD
representations with prescribed order variables. The output OBDD has a polynomial size in the number
of input variables, provided that the input representation has a constant number of switches.
This extends previous results. Moreover, this could help to analyze the complexity
of many queries when the input is a switch-list representation. |