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-01905491Date
2019Journal name
Journal of Multiple-Valued Logic and Soft ComputingVolume
33Number
3Publisher
OCP Science
Pages
197-218
Metadata
Show full item recordAbstract (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 polynomialRelated items
Showing items related by title and author.
-
Waldhauser, Tamás; Marichal, Jean-Luc; Lehtonen, Erkko; Couceiro, Miguel (2011) Communication / Conférence
-
Lehtonen, Erkko; Foldes, Stephan; Couceiro, Miguel (2006) Article accepté pour publication ou publié
-
Couceiro, Miguel (2008) Article accepté pour publication ou publié
-
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
-
Waldhauser, Tamás; Marichal, Jean-Luc; Couceiro, Miguel (2012) Article accepté pour publication ou publié