Median based calculus for lattice polynomials and monotone Boolean functions - Archive ouverte HAL Access content directly
Conference Papers Year : 2017

Median based calculus for lattice polynomials and monotone Boolean functions

(1) , (2) , (2) , (3)
1
2
3

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.
Fichier principal
Vignette du fichier
median-computations-Revised.pdf (263.81 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01504010 , version 1 (08-04-2017)

Identifiers

  • HAL Id : hal-01504010 , version 1

Cite

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⟩
330 View
264 Download

Share

Gmail Facebook Twitter LinkedIn More