ملخص
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.
اللغة الأصلية | الإنجليزيّة |
---|---|
عنوان منشور المضيف | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019 |
المحررون | Arkadev Chattopadhyay, Paul Gastin |
ناشر | Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing |
رقم المعيار الدولي للكتب (الإلكتروني) | 9783959771313 |
المعرِّفات الرقمية للأشياء | |
حالة النشر | نُشِر - ديسمبر 2019 |
الحدث | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019 - Bombay, الهند المدة: ١١ ديسمبر ٢٠١٩ → ١٣ ديسمبر ٢٠١٩ |
سلسلة المنشورات
الاسم | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
مستوى الصوت | 150 |
رقم المعيار الدولي للدوريات (المطبوع) | 1868-8969 |
!!Conference
!!Conference | 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2019 |
---|---|
الدولة/الإقليم | الهند |
المدينة | Bombay |
المدة | ١١/١٢/١٩ → ١٣/١٢/١٩ |
ملاحظة ببليوغرافية
Publisher Copyright:© Jeffrey M. Dudek and Dror Fried; licensed under Creative Commons License CC-BY.