License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2020.22
URN: urn:nbn:de:0030-drops-120968
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/12096/
Go to the corresponding LIPIcs Volume Portal

Nakamura, Kengo ; Denzumi, Shuhei ; Nishino, Masaaki

Variable Shift SDD: A More Succinct Sentential Decision Diagram

pdf-format:
LIPIcs-SEA-2020-22.pdf (0.6 MB)

Abstract

The Sentential Decision Diagram (SDD) is a tractable representation of Boolean functions that subsumes the famous Ordered Binary Decision Diagram (OBDD) as a strict subset. SDDs are attracting much attention because they are more succinct than OBDDs, as well as having canonical forms and supporting many useful queries and transformations such as model counting and Apply operation. In this paper, we propose a more succinct variant of SDD named Variable Shift SDD (VS-SDD). The key idea is to create a unique representation for Boolean functions that are equivalent under a specific variable substitution. We show that VS-SDDs are never larger than SDDs and there are cases in which the size of a VS-SDD is exponentially smaller than that of an SDD. Moreover, despite such succinctness, we show that numerous basic operations that are supported in polytime with SDD are also supported in polytime with VS-SDD. Experiments confirm that VS-SDDs are significantly more succinct than SDDs when applied to classical planning instances, where inherent symmetry exists.

BibTeX - Entry

@InProceedings{nakamura_et_al:LIPIcs:2020:12096,
  author =	{Kengo Nakamura and Shuhei Denzumi and Masaaki Nishino},
  title =	{{Variable Shift SDD: A More Succinct Sentential Decision Diagram}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{22:1--22:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Simone Faro and Domenico Cantone},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12096},
  URN =		{urn:nbn:de:0030-drops-120968},
  doi =		{10.4230/LIPIcs.SEA.2020.22},
  annote =	{Keywords: Boolean function, Data structure, Sentential decision diagram}
}

Keywords: Boolean function, Data structure, Sentential decision diagram
Collection: 18th International Symposium on Experimental Algorithms (SEA 2020)
Issue Date: 2020
Date of publication: 12.06.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI