Properties of Switch-List Representations of Boolean Functions
Open Access
- 18 October 2020
- journal article
- Published by AI Access Foundation in Journal of Artificial Intelligence Research
- Vol. 69, 501–529
Abstract
In this paper, we focus on a less usual way to represent Boolean functions, namely on representations by switch-lists, which are closely related to interval representations. 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 this paper is to include this type of representation in the Knowledge Compilation Map by Darwiche and Marquis and to argue that switch-lists may in certain situations constitute a reasonable choice for a target language in knowledge compilation. First, we compare switch-list representations with a number of standard representations (such as CNF, DNF, and OBDD) with respect to their relative succinctness. As a by-product of this analysis, we also give a short proof of a longstanding open question proposed by Darwiche and Marquis, namely the incomparability of MODS (models) and PI (prime implicates) representations. Next, using the succinctness result between switch-lists and OBDDs, we develop a polynomial time compilation algorithm from switch-lists to OBDDs. Finally, we analyze which standard transformations and queries (those considered by Darwiche and Marquis) can be performed in polynomial time with respect to the size of the input if the input knowledge is represented by a switch-list. We show that this collection is very broad and the combination of polynomial time transformations and queries is quite unique. Some of the queries can be answered directly using the switch-list input, others require a compilation of the input to OBDD representations which are then used to answer the queries.Keywords
This publication has 12 references indexed in Scilit:
- Recognition of tractable DNFs representable by a constant number of intervalsDiscrete Optimization, 2017
- A decomposition method for CNF minimality proofsTheoretical Computer Science, 2013
- A subclass of Horn CNFs optimally compressible in polynomial timeAnnals of Mathematics and Artificial Intelligence, 2009
- Recognition of interval Boolean functionsAnnals of Mathematics and Artificial Intelligence, 2008
- Complexity of two-level logic minimizationIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2006
- Computing the minimum DNF representation of Boolean functions defined by intervalsDiscrete Applied Mathematics, 2005
- The Minimum Equivalent DNF Problem and Shortest ImplicantsJournal of Computer and System Sciences, 2001
- Efficient algorithms for the transformation between different types of binary decision diagramsActa Informatica, 1997
- Quasi-acyclic propositional Horn knowledge bases: optimal compressionIEEE Transactions on Knowledge and Data Engineering, 1995
- Optimal compression of propositional Horn knowledge bases: complexity and approximationArtificial Intelligence, 1993