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
Nom de la revue
Order
Volume
30
Numéro
2
Éditeur
Springer
Pages
557-572
Identifiant publication
Métadonnées
Afficher la notice complète
Auteur(s)
Waldhauser, Tamás
Lehtonen, Erkko cc
Couceiro, Miguel
Résumé (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.
Mots-clés
Arity gap; simple minor; essential variable; parametrized arity gap; variable identification minor