Skip to Main content Skip to Navigation
Conference papers

Median based calculus for lattice polynomials and monotone Boolean functions

Miguel Couceiro 1 Pierre Mercuriali 2 Romain Péchoux 2 Abdallah Saffidine 3
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Abstract : In this document, we consider a median-based calculus for efficiently representing polynomial functions over distributive lattices. We extend an equational specification of median forms from the domain of Boolean functions to the domain of lattice polynomials. We show that it is sound and complete, and 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 also investigate related complexity issues and show that the problem of deciding whether a formula is in MNF is in Σ^P_2. Moreover, we explore polynomial approximations of solutions to this problem through a sound term rewriting system extracted from the proposed equational specification.
Document type :
Conference papers
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download
Contributor : Miguel Couceiro Connect in order to contact the contributor
Submitted on : Saturday, April 8, 2017 - 1:09:01 AM
Last modification on : Saturday, October 16, 2021 - 11:26:08 AM
Long-term archiving on: : Sunday, July 9, 2017 - 12:16:05 PM


Files produced by the author(s)


  • HAL Id : hal-01504010, version 1


Miguel Couceiro, Pierre Mercuriali, Romain Péchoux, Abdallah Saffidine. Median based calculus for lattice polynomials and monotone Boolean functions. ISMVL 2017 - 47th IEEE International Symposium on Multiple-Valued Logic, May 2017, Novi Sad, Serbia. pp.6. ⟨hal-01504010⟩



Record views


Files downloads