Charles Explorer logo
🇬🇧

Succinctness of Switch-List Representations of Boolean Functions

Publication at Faculty of Mathematics and Physics |
2018

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 di DOWNWARDS ARROW WITH CORNER LEFTWARDS erent function value than the preceding Boolean vector in the truth table.

The main aim of this paper is to compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness, and hence to include switch-list representations in the Knowledge Compilation Map [7].