# OCommICAART 2019 Abstracts

Short Papers

Paper Nr: | 1 |

Title: | ## Relative Succinctness of OBDDs and Switch-List Representations |

Authors: | ## 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. |