Transformations of Boolean functions

Jeffrey M. Dudek, Dror Fried

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

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

!!Conference39th 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.

بصمة

أدرس بدقة موضوعات البحث “Transformations of Boolean functions'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا