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 metadatas

Cited literature [19 references]  Display  Hide  Download

https://hal.inria.fr/hal-01504010
Contributor : Miguel Couceiro <>
Submitted on : Saturday, April 8, 2017 - 1:09:01 AM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM
Long-term archiving on : Sunday, July 9, 2017 - 12:16:05 PM

File

median-computations-Revised.pd...
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01504010, version 1

Citation

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⟩

Share

Metrics

Record views

490

Files downloads

239