The arity gap of polynomial functions over bounded distributive lattices
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
TypeCommunication / Conférence
External document linkhttp://arxiv.org/abs/0910.5131
Conference title40th IEEE International Symposium on Multiple-Valued Logic (ISMVL2010)
Book title40th IEEE International Symposium on Multiple-Valued Logic, ISMVL 2010, Barcelona, Spain, 26-28 May 2010
MetadataShow full item record
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 / KeywordsPolynomial function; arity gap; classification
Showing items related by title and author.