Median Based Calculus for Lattice Polynomials and Monotone Boolean Functions

Miguel Couceiro, Pierre Mercuriali, Romain Péchoux, Abdallah Saffidine

Research output: Chapter in Book/Conference proceedings/Edited volumeConference contributionScientificpeer-review

1 Citation (Scopus)

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 ΣP2. Moreover, we explore polynomial approximations of solutions to this problem through a sound term rewriting system extracted from the proposed equational specification.

Original languageEnglish
Title of host publicationProceedings - 2017 IEEE 47th International Symposium on Multiple-Valued Logic, ISMVL 2017
PublisherIEEE
Pages37-42
ISBN (Electronic)9781509054954
DOIs
Publication statusPublished - 2017
Externally publishedYes
Event47th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2017 - Novi Sad, Serbia
Duration: 22 May 201724 May 2017

Conference

Conference47th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2017
CountrySerbia
CityNovi Sad
Period22/05/1724/05/17

Keywords

  • canonical normal form
  • Median normal form
  • structural representation
  • term rewriting system

Fingerprint

Dive into the research topics of 'Median Based Calculus for Lattice Polynomials and Monotone Boolean Functions'. Together they form a unique fingerprint.

Cite this