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.FSTTCS.2019.39
URN: urn:nbn:de:0030-drops-116019
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/11601/
Go to the corresponding LIPIcs Volume Portal

Dudek, Jeffrey M. ; Fried, Dror

Transformations of Boolean Functions

pdf-format:
LIPIcs-FSTTCS-2019-39.pdf (0.5 MB)

Abstract

Boolean functions are characterized by the unique structure of their solution space. Some properties of the solution space, such as the possible existence of a solution, are well sought after but difficult to obtain. To better reason about such properties, we define transformations as functions that change one Boolean function to another while maintaining some properties of the solution space. We explore transformations of Boolean functions, compactly described as Boolean formulas, where the property is to maintain is the number of solutions in the solution spaces. We first discuss general characteristics of such transformations. Next, we reason about the computational complexity of transforming one Boolean formula to another. Finally, we demonstrate the versatility of transformations by extensively discussing transformations of Boolean formulas to "blocks," which are solution spaces in which the set of solutions makes a prefix of the solution space under a lexicographic order of the variables.

BibTeX - Entry

@InProceedings{dudek_et_al:LIPIcs:2019:11601,
  author =	{Jeffrey M. Dudek and Dror Fried},
  title =	{{Transformations of Boolean Functions}},
  booktitle =	{39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)},
  pages =	{39:1--39:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-131-3},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{150},
  editor =	{Arkadev Chattopadhyay and Paul Gastin},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2019/11601},
  URN =		{urn:nbn:de:0030-drops-116019},
  doi =		{10.4230/LIPIcs.FSTTCS.2019.39},
  annote =	{Keywords: Boolean Formulas, Boolean Functions, Transformations, Model Counting}
}

Keywords: Boolean Formulas, Boolean Functions, Transformations, Model Counting
Collection: 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Issue Date: 2019
Date of publication: 04.12.2019

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