Publications > Artigos em Revistas Internacionais

On the effect of variable identification on the essential arity of functions on finite sets

Couceiro, Miguel; Lehtonen, Erkko

Int. J. Found. Comput. Sci., 18 (2007), 975-986

We show that every function of several variables on a finite set of k elements with n > k essential variables has a variable identification minor with at least n-k essential variables. This is a generalization of a theorem of Salomaa on the essential variables of Boolean functions. We also strengthen Salomaa's theorem by characterizing all the Boolean functions f having a variable identification minor that has just one essential variable less than f.