Reference : On the effect of variable identification on the essential arity of functions on finit...
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
http://hdl.handle.net/10993/4548
On the effect of variable identification on the essential arity of functions on finite sets
English
Couceiro, Miguel mailto [University of Tampere, Finland]
Lehtonen, Erkko mailto [Tampere University of Technology, Finland]
2007
International Journal of Foundations of Computer Science
World Scientific
18
5
975-986
Yes (verified by ORBilu)
International
0129-0541
[en] functions on finite sets ; Boolean functions ; essential variables ; variable identification ; arity gap ; minors of functions
[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.
http://hdl.handle.net/10993/4548
10.1142/S012905410700508X
Electronic version of an article published as International Journal of Foundations of Computer Science 18(5) (2007) 975-986. DOI: 10.1142/S012905410700508X. © copyright World Scientific Publishing Company, http://www.worldscientific.com/worldscinet/ijfcs.

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
Gap.pdfAuthor postprint279.1 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.