On the arity gap of finite functions : results and applications. - Archive ouverte HAL Access content directly
Journal Articles Journal of Multiple-Valued Logic and Soft Computing Year : 2016

On the arity gap of finite functions : results and applications.

(1) , (2)
1
2
Miguel Couceiro
Erkko Lehtonen

Abstract

Let A be a finite set and B an arbitrary set with at least two elements. The arity gap of a function f : A^n → 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.
Not file

Dates and versions

hal-01175695 , version 1 (11-07-2015)

Identifiers

  • HAL Id : hal-01175695 , version 1

Cite

Miguel Couceiro, Erkko Lehtonen. On the arity gap of finite functions : results and applications.. Journal of Multiple-Valued Logic and Soft Computing, 2016, 27 (2-3), pp.15. ⟨hal-01175695⟩
244 View
0 Download

Share

Gmail Facebook Twitter LinkedIn More