• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
Date
2019
Link to item file
https://hal.inria.fr/hal-01905491
Dewey
Principes généraux des mathématiques
Sujet
Efficient representation; Complexity; Normal form; Boolean function; Lattice polynomial
Journal issue
Journal of Multiple-Valued Logic and Soft Computing
Volume
33
Number
3
Publication date
2019
Article pages
197-218
Publisher
OCP Science
Forthcoming
oui
URI
https://basepub.dauphine.fr/handle/123456789/21005
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Couceiro, M.
Mercuriali, Pierre
Péchoux, Romain
Saffidine, Abdallah
Type
Article accepté pour publication ou publié
Abstract (EN)
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 ∑P2. Moreover, we show that it still holds for arbitrary Boolean functions, not necessarily monotone.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.