The arity gap of polynomial functions over bounded distributive lattices

Lehtonen, Erkko; Couceiro, Miguel

Lehtonen, Erkko; Couceiro, Miguel (2011), The arity gap of polynomial functions over bounded distributive lattices, 40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010, Barcelona, Spain, 26-28 May 2010, IEEE : Washington, p. 113-116. http://dx.doi.org/10.1109/ISMVL.2010.29

Type

Communication / Conférence

External document link

http://arxiv.org/abs/0910.5131

Date

2011

Conference title

40th IEEE International Symposium on Multiple-Valued Logic (ISMVL2010)

Conference date

2010-05

Conference city

Barcelone

Conference country

Espagne

Book title

40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010, Barcelona, Spain, 26-28 May 2010

Publisher

IEEE

Published in

Washington

ISBN

978-0-7695-4024-5

Pages

113-116

Abstract (EN)

Let A and B be arbitrary sets with at least two elements. The arity gap of a function f: A^n \to 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.

Subjects / Keywords

Polynomial function; arity gap; classification