On the arity gap of finite functions: results and applications
Lehtonen, Erkko; Couceiro, Miguel; Couceiro, Miguel (2008), On the arity gap of finite functions: results and applications, Actes de la Conference internationale sur les Relations, Ordres et Graphes: Interaction avec l'Informatique ROGICS’08, p. 65-72
TypeCommunication / Conférence
Conference titleConference internationale sur les Relations, Ordres et Graphes: Interaction avec l'Informatique ROGICS’08
Book titleActes de la Conference internationale sur les Relations, Ordres et Graphes: Interaction avec l'Informatique ROGICS’08
MetadataShow full item record
Abstract (EN)Let A be a nite 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 identi ed. A non-trivial fact is that the arity gap of such B-valued functions on A is at most jAj. Even less trivial to verify is the fact that the arity gap of B-valued functions on A with more than jAj essential variables is at most 2. These facts ask for a classi cation 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 classi cations 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.
Subjects / Keywordsfinite function; Boolean function; variable substitution; essential variable; arity gap
Showing items related by title and author.