On the effect of variable indentification on the essential arity of functions
Lehtonen, Erkko; Couceiro, Miguel (2007), On the effect of variable indentification on the essential arity of functions, International Journal of Foundations of Computer Science, 18, 5. http://dx.doi.org/10.1142/S012905410700508X
TypeArticle accepté pour publication ou publié
External document linkhttp://arxiv.org/abs/math/0701332
Journal nameInternational Journal of Foundations of Computer Science
MetadataShow full item record
Abstract (EN)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.
Subjects / Keywordsminors of functions; arity gap; variable identification; essential variables; Boolean functions; Functions on finite sets
Showing items related by title and author.