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

Miguel Couceiro; Erkko Lehtonen

doi:10.1142/S012905410700508X

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

Miguel Couceiro, Erkko Lehtonen

Mathematics

Tampere University

Research output: Contribution to journal › Article › peer-review

14 Scopus citations

Abstract

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.

Original language	British English
Pages (from-to)	975-986
Number of pages	12
Journal	International Journal of Foundations of Computer Science
Volume	18
Issue number	5
DOIs	https://doi.org/10.1142/S012905410700508X
State	Published - Oct 2007

Keywords

Arity gap
Boolean functions
Essential variables
Functions on finite sets
Minors of functions
Variable identification

Access to Document

10.1142/S012905410700508X

Cite this

@article{d3fbb3419d794a5ba1f6f57220e40e30,

title = "On the effect of variable identification on the essential arity of functions on finite sets",

abstract = "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.",

keywords = "Arity gap, Boolean functions, Essential variables, Functions on finite sets, Minors of functions, Variable identification",

author = "Miguel Couceiro and Erkko Lehtonen",

year = "2007",

month = oct,

doi = "10.1142/S012905410700508X",

language = "British English",

volume = "18",

pages = "975--986",

journal = "International Journal of Foundations of Computer Science",

issn = "0129-0541",

publisher = "World Scientific Publishing Co. Pte Ltd",

number = "5",

}

TY - JOUR

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

AU - Couceiro, Miguel

AU - Lehtonen, Erkko

PY - 2007/10

Y1 - 2007/10

N2 - 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.

AB - 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.

KW - Arity gap

KW - Boolean functions

KW - Essential variables

KW - Functions on finite sets

KW - Minors of functions

KW - Variable identification

UR - http://www.scopus.com/inward/record.url?scp=34748831191&partnerID=8YFLogxK

U2 - 10.1142/S012905410700508X

DO - 10.1142/S012905410700508X

M3 - Article

AN - SCOPUS:34748831191

SN - 0129-0541

VL - 18

SP - 975

EP - 986

JO - International Journal of Foundations of Computer Science

JF - International Journal of Foundations of Computer Science

IS - 5

ER -

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

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this