Parametrized Arity Gap

Miguel Couceiro; Erkko Lehtonen; Tamás Waldhauser

doi:10.1007/s11083-012-9261-5

Parametrized Arity Gap

Miguel Couceiro, Erkko Lehtonen, Tamás Waldhauser

Mathematics

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

6 Scopus citations

Abstract

We propose a parametrized version of arity gap. The parametrized arity gap gap (f, ℓ) of a function f: Aⁿ → B measures the minimum decrease in the number of essential variables of f when ℓ consecutive identifications of pairs of essential variables are performed. We determine gap (f, ℓ) for an arbitrary function f and a nonnegative integer ℓ. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.

Original language	British English
Pages (from-to)	557-572
Number of pages	16
Journal	Order
Volume	30
Issue number	2
DOIs	https://doi.org/10.1007/s11083-012-9261-5
State	Published - Jul 2013

Keywords

Arity gap
Essential variable
Parametrized arity gap
Simple minor
Variable identification minor

Access to Document

10.1007/s11083-012-9261-5

Cite this

@article{2fabc1c3b590438698a87908deba94bc,

title = "Parametrized Arity Gap",

abstract = "We propose a parametrized version of arity gap. The parametrized arity gap gap (f, ℓ) of a function f: An → B measures the minimum decrease in the number of essential variables of f when ℓ consecutive identifications of pairs of essential variables are performed. We determine gap (f, ℓ) for an arbitrary function f and a nonnegative integer ℓ. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.",

keywords = "Arity gap, Essential variable, Parametrized arity gap, Simple minor, Variable identification minor",

author = "Miguel Couceiro and Erkko Lehtonen and Tam{\'a}s Waldhauser",

note = "Funding Information: The first named author is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. The third named author acknowledges that the present project is supported by the T{\'A}MOP-4.2.1/B-09/1/KONV-2010-0005 program of the National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).",

year = "2013",

month = jul,

doi = "10.1007/s11083-012-9261-5",

language = "British English",

volume = "30",

pages = "557--572",

journal = "Order",

issn = "0167-8094",

publisher = "Springer Netherlands",

number = "2",

}

TY - JOUR

T1 - Parametrized Arity Gap

AU - Couceiro, Miguel

AU - Lehtonen, Erkko

AU - Waldhauser, Tamás

N1 - Funding Information: The first named author is supported by the internal research project F1R-MTH-PUL-09MRDO of the University of Luxembourg. The third named author acknowledges that the present project is supported by the TÁMOP-4.2.1/B-09/1/KONV-2010-0005 program of the National Development Agency of Hungary, by the Hungarian National Foundation for Scientific Research under grants no. K77409 and K83219, by the National Research Fund of Luxembourg, and cofunded under the Marie Curie Actions of the European Commission (FP7-COFUND).

PY - 2013/7

Y1 - 2013/7

N2 - We propose a parametrized version of arity gap. The parametrized arity gap gap (f, ℓ) of a function f: An → B measures the minimum decrease in the number of essential variables of f when ℓ consecutive identifications of pairs of essential variables are performed. We determine gap (f, ℓ) for an arbitrary function f and a nonnegative integer ℓ. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.

AB - We propose a parametrized version of arity gap. The parametrized arity gap gap (f, ℓ) of a function f: An → B measures the minimum decrease in the number of essential variables of f when ℓ consecutive identifications of pairs of essential variables are performed. We determine gap (f, ℓ) for an arbitrary function f and a nonnegative integer ℓ. We also propose other variants of arity gap and discuss further problems pertaining to the effect of identification of variables on the number of essential variables of functions.

KW - Arity gap

KW - Essential variable

KW - Parametrized arity gap

KW - Simple minor

KW - Variable identification minor

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

U2 - 10.1007/s11083-012-9261-5

DO - 10.1007/s11083-012-9261-5

M3 - Article

AN - SCOPUS:84878751782

SN - 0167-8094

VL - 30

SP - 557

EP - 572

JO - Order

JF - Order

IS - 2

ER -

Parametrized Arity Gap

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this