License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SAT.2022.17
URN: urn:nbn:de:0030-drops-166913
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/16691/
Go to the corresponding LIPIcs Volume Portal

Mengel, Stefan

Changing Partitions in Rectangle Decision Lists

pdf-format:
LIPIcs-SAT-2022-17.pdf (0.7 MB)

Abstract

Rectangle decision lists are a form of decision lists that were recently shown to have applications in the proof complexity of certain OBDD-based QBF-solvers. We consider a version of rectangle decision lists with changing partitions, which corresponds to QBF-solvers that may change the variable order of the OBDDs they produce. We show that even allowing one single partition change generally leads to exponentially more succinct decision lists. More generally, we show that there is a succinctness hierarchy: for every k ∈ ℕ, when going from k partition changes to k+1, there are functions that can be represented exponentially more succinctly. As an application, we show a similar hierarchy for OBDD-based QBF-solvers.

BibTeX - Entry

@InProceedings{mengel:LIPIcs.SAT.2022.17,
  author =	{Mengel, Stefan},
  title =	{{Changing Partitions in Rectangle Decision Lists}},
  booktitle =	{25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-242-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{236},
  editor =	{Meel, Kuldeep S. and Strichman, Ofer},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/16691},
  URN =		{urn:nbn:de:0030-drops-166913},
  doi =		{10.4230/LIPIcs.SAT.2022.17},
  annote =	{Keywords: rectangle decision lists, QBF proof complexity, OBDD}
}

Keywords: rectangle decision lists, QBF proof complexity, OBDD
Collection: 25th International Conference on Theory and Applications of Satisfiability Testing (SAT 2022)
Issue Date: 2022
Date of publication: 28.07.2022

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