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

Miguel Couceiro 1 Pierre Mercuriali 2 Romain Péchoux 2 Abdallah Saffidine 3, 4
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
2 MOCQUA - Designing the Future of Computational Models
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this document, we consider a median-based calculus to represent monotone Boolean functions efficiently. We study an equa-tional 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 Σ P 2. Moreover, we show that it still holds for arbitrary Boolean functions, not necessarily monotone.
Complete list of metadatas

Cited literature [3 references]  Display  Hide  Download

https://hal.inria.fr/hal-01905491
Contributor : Miguel Couceiro <>
Submitted on : Thursday, October 25, 2018 - 6:31:07 PM
Last modification on : Sunday, April 14, 2019 - 4:10:35 PM
Long-term archiving on : Saturday, January 26, 2019 - 4:22:17 PM

File

median_computations_MVLSC-CMPS...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01905491, version 1

Citation

Miguel Couceiro, Pierre Mercuriali, Romain Péchoux, Abdallah Saffidine. On the complexity of minimizing median normal forms of monotone Boolean functions and lattice polynomials. Journal of Multiple-Valued Logic and Soft Computing, Old City Publishing, In press. ⟨hal-01905491⟩

Share

Metrics

Record views

110

Files downloads

39