2026-09-19T03:15:35Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11601 2026-09-05T05:08:12Z ddc:004 open_access

Transformations of Boolean Functions Dudek, Jeffrey M. Fried, Dror Boolean Formulas Boolean Functions Transformations Model Counting 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jeffrey M. Dudek and Dror Fried 2019 Is Part Of LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2019.39 urn:nbn:de:0030-drops-116019 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.39 eng https://creativecommons.org/licenses/by/3.0/legalcode