On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials

Miguel Couceiro, Pierre Mercuriali, Romain Péchoux, Abdallah Saffidine

Research output: Contribution to journalArticleScientificpeer-review

Abstract

In this document, we consider a median-based calculus to represent monotone Boolean functions efficiently. We study an equational specification of median forms and extend it from the domain of monotone Boolean functions to the domain of polynomial functions over distributive lattices. This specification is sound and complete. We illustrate its usefulness when simplifying median formulas algebraically. Furthermore, we propose a definition of median normal forms (MNF), that are thought of as minimal median formulas with respect to a structural ordering of expressions. We investigate related complexity issues and show that the problem of deciding whether a formula is in MNF, that is the problem of minimizing the median form of a monotone Boolean function, is in ∑2 P. Moreover, we show that it still holds for arbitrary Boolean functions, not necessarily monotone.

Original languageEnglish
Pages (from-to)197-218
Number of pages22
JournalJournal of Multiple-Valued Logic and Soft Computing
Volume33
Issue number3
Publication statusPublished - 2019
Externally publishedYes

Keywords

  • Efficient representation
  • Lattice polynomial
  • Median algebra
  • Monotone boolean function
  • Normal form

Fingerprint

Dive into the research topics of 'On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials'. Together they form a unique fingerprint.

Cite this