OCommICAART 2019 Abstracts

Short Papers
Paper Nr: 1

Relative Succinctness of OBDDs and Switch-List Representations


MiloŇ° Chromý

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.