• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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

Couceiro, M.; Mercuriali, Pierre; Péchoux, Romain; Saffidine, Abdallah (2019), On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials, Journal of Multiple-Valued Logic and Soft Computing, 33, 3, p. 197-218

Type
Article accepté pour publication ou publié
External document link
https://hal.inria.fr/hal-01905491
Date
2019
Journal name
Journal of Multiple-Valued Logic and Soft Computing
Volume
33
Number
3
Publisher
OCP Science
Pages
197-218
Metadata
Show full item record
Author(s)
Couceiro, M.
Mercuriali, Pierre
Péchoux, Romain
Saffidine, Abdallah
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.
Subjects / Keywords
Efficient representation; Complexity; Normal form; Boolean function; Lattice polynomial

Related items

Showing items related by title and author.

  • Thumbnail
    An algorithm for producing median normal form representations for Boolean functions 
    Waldhauser, Tamás; Marichal, Jean-Luc; Lehtonen, Erkko; Couceiro, Miguel (2011) Communication / Conférence
  • Thumbnail
    Composition of Post classes and normal forms of Boolean functions 
    Lehtonen, Erkko; Foldes, Stephan; Couceiro, Miguel (2006) Article accepté pour publication ou publié
  • Thumbnail
    On the lattice of equational classes of Boolean functions and its closed intervals 
    Couceiro, Miguel (2008) Article accepté pour publication ou publié
  • Thumbnail
    Hierarchies of local monotonicities and lattice derivatives for Boolean and pseudo-Boolean functions 
    Waldhauser, Tamás; Marichal, Jean-Luc; Couceiro, Miguel (2012) Communication / Conférence
  • Thumbnail
    Locally monotone Boolean and pseudo-Boolean functions 
    Waldhauser, Tamás; Marichal, Jean-Luc; Couceiro, Miguel (2012) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo