Parametrized Arity Gap

Miguel Couceiro, Erkko Lehtonen, Tamás Waldhauser

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.

Original languageBritish English
Pages (from-to)557-572
Number of pages16
Issue number2
StatePublished - Jul 2013


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


Dive into the research topics of 'Parametrized Arity Gap'. Together they form a unique fingerprint.

Cite this