The arity gap of polynomial functions over bounded distributive lattices

Miguel Couceiro, Erkko Lehtonen

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

5 Scopus citations

Abstract

Let A and B be arbitrary sets with at least two elements. The arity gap of a function f: An → B is the minimum decrease in its essential arity when essential arguments of f are identified. In this paper we study the arity gap of polynomial functions over bounded distributive lattices and present a complete classification of such functions in terms of their arity gap. To this extent, we present a characterization of the essential arguments of polynomial functions, which we then use to show that almost all lattice polynomial functions have arity gap 1, with the exception of truncated median functions, whose arity gap is 2.

Original languageBritish English
Title of host publicationISMVL 2010 - 40th IEEE International Symposium on Multiple-Valued Logic
Pages113-116
Number of pages4
DOIs
StatePublished - 2010
Event40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010 - Barcelona, Spain
Duration: 26 May 201028 May 2010

Publication series

NameProceedings of The International Symposium on Multiple-Valued Logic
ISSN (Print)0195-623X

Conference

Conference40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010
Country/TerritorySpain
CityBarcelona
Period26/05/1028/05/10

Fingerprint

Dive into the research topics of 'The arity gap of polynomial functions over bounded distributive lattices'. Together they form a unique fingerprint.

Cite this