Couceiro, Miguel[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]
Lehtonen, Erkko[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]
[en] arity gap ; parametrized arity gap ; essential variable ; simple minor ; variable identification minor
[en] We propose a parametrized version of arity gap. The parametrized arity gap gap(f,l) of a function f: Aⁿ → B measures the minimum decrease in the number of essential variables of f when l consecutive identifications of pairs of essential variables are performed. We determine gap(f,l) for an arbitrary function f and a positive integer l. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.