Tampere University of Technology

TUTCRIS Research Portal

On the arity gap of finite functions: Results and applications

Research output: Contribution to journalReview ArticleScientificpeer-review


Original languageEnglish
Pages (from-to)193-207
Number of pages15
JournalJournal of Multiple-Valued Logic and Soft Computing
Issue number2-3
Publication statusPublished - 2016
Publication typeA2 Review article in a scientific journal


Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f : An → B is the minimum decrease in the number of essential variables when essential variables of f are identified. A non- Trivial fact is that the arity gap of such B-valued functions on A is at most |A|. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than |A| essential variables is at most 2. These facts ask for a classification of B-valued functions on A in terms of their arity gap. In this paper, we survey what is known about this problem. We present a general characterization of the arity gap of B-valued functions on A and provide explicit classifications of the arity gap of Boolean and pseudo-Boolean functions. Moreover, we reveal unsettled questions related to this topic, and discuss links and possible applications of some results to other subjects of research.

Publication forum classification

Field of science, Statistics Finland