Thumbnail - Request a copy

Parametrized arity gap

Waldhauser, Tamás; Lehtonen, Erkko; Couceiro, Miguel (2013), Parametrized arity gap, Order, 30, 2, p. 557-572. http://dx.doi.org/10.1007/s11083-012-9261-5

Type
Article accepté pour publication ou publié
Date
2013
Journal name
Order
Volume
30
Number
2
Publisher
Springer
Pages
557-572
Publication identifier
Metadata
Show full item record
Author(s)
Waldhauser, Tamás
Lehtonen, Erkko cc
Couceiro, Miguel
Abstract (EN)
We propose a parametrized version of arity gap. The parametrized arity gap gap (f, ℓ) of a function f:AnB 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.
Subjects / Keywords
Arity gap; simple minor; essential variable; parametrized arity gap; variable identification minor