Article (Scientific journals)
On the effect of variable identification on the essential arity of functions on finite sets
Couceiro, Miguel; Lehtonen, Erkko
2007In International Journal of Foundations of Computer Science, 18 (5), p. 975-986
Peer Reviewed verified by ORBi
 

Files


Full Text
Gap.pdf
Author postprint (285.8 kB)
Download

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.


All documents in ORBilu are protected by a user license.

Send to



Details



Keywords :
functions on finite sets; Boolean functions; essential variables; variable identification; arity gap; minors of functions
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.
Disciplines :
Mathematics
Identifiers :
UNILU:UL-ARTICLE-2010-133
Author, co-author :
Couceiro, Miguel ;  University of Tampere, Finland
Lehtonen, Erkko ;  Tampere University of Technology, Finland
Language :
English
Title :
On the effect of variable identification on the essential arity of functions on finite sets
Publication date :
2007
Journal title :
International Journal of Foundations of Computer Science
ISSN :
0129-0541
Publisher :
World Scientific
Volume :
18
Issue :
5
Pages :
975-986
Peer reviewed :
Peer Reviewed verified by ORBi
Available on ORBilu :
since 02 August 2013

Statistics


Number of views
28 (0 by Unilu)
Number of downloads
84 (0 by Unilu)

Scopus citations®
 
14
Scopus citations®
without self-citations
0
WoS citations
 
13

Bibliography


Similar publications



Contact ORBilu