Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. The Complexity of Self-Dual Monotone 7-Input Functions
 
conference paper

The Complexity of Self-Dual Monotone 7-Input Functions

Testa, Eleonora  
•
Haaswijk, Winston Jason  
•
Soeken, Mathias  
Show more
June 21, 2019
[Proceedings of the 28th International Workshop on Logic & Synthesis (IWLS 2019)]
28th International Workshop on Logic & Synthesis (IWLS 2019)

The study of the complexity of Boolean functions has recently found applications in logic synthesis and optimization algorithms, as for instance in logic rewriting. Previous works have focused on the minimum length of Boolean chains for functions up to 5 inputs, being represented in terms of 2- and 3-input operators. In this work, we study the complexity of selfdual monotone 7-input Boolean functions in terms of 3-input majority operators. We use enumeration-based and SAT-based exact methods to find (i) the minimum number of operators in the shortest formula of a Boolean function, and (ii) the minimum length of its Boolean chain. Different generalizations and restrictions of majority Boolean chains are considered to represent functions. For instance, we consider leafy Boolean chains in which each step has at least one fanin that is an input variable, or majority Boolean chains that use complemented edges.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

IWLS2019_ET.pdf

Access type

openaccess

Size

198.56 KB

Format

Adobe PDF

Checksum (MD5)

ef8cce884c40f64b3cf6f9dd1b6cadca

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés