# On finite functions with non-trivial arity gap

Slavcho Shtrakov; Jörg Koppitz

Discussiones Mathematicae - General Algebra and Applications (2010)

- Volume: 30, Issue: 2, page 217-245
- ISSN: 1509-9415

## Access Full Article

top## Abstract

top## How to cite

topSlavcho Shtrakov, and Jörg Koppitz. "On finite functions with non-trivial arity gap." Discussiones Mathematicae - General Algebra and Applications 30.2 (2010): 217-245. <http://eudml.org/doc/276580>.

@article{SlavchoShtrakov2010,

abstract = {
Given an n-ary k-valued function f, gap(f) denotes the minimal number of essential variables in f which become fictive when identifying any two distinct essential variables in f.
We particularly solve a problem concerning the explicit determination of n-ary k-valued functions f with 2 ≤ gap(f) ≤ n ≤ k. Our methods yield new combinatorial results about the number of such functions.
},

author = {Slavcho Shtrakov, Jörg Koppitz},

journal = {Discussiones Mathematicae - General Algebra and Applications},

keywords = {essential variable; identification minor; essential arity gap},

language = {eng},

number = {2},

pages = {217-245},

title = {On finite functions with non-trivial arity gap},

url = {http://eudml.org/doc/276580},

volume = {30},

year = {2010},

}

TY - JOUR

AU - Slavcho Shtrakov

AU - Jörg Koppitz

TI - On finite functions with non-trivial arity gap

JO - Discussiones Mathematicae - General Algebra and Applications

PY - 2010

VL - 30

IS - 2

SP - 217

EP - 245

AB -
Given an n-ary k-valued function f, gap(f) denotes the minimal number of essential variables in f which become fictive when identifying any two distinct essential variables in f.
We particularly solve a problem concerning the explicit determination of n-ary k-valued functions f with 2 ≤ gap(f) ≤ n ≤ k. Our methods yield new combinatorial results about the number of such functions.

LA - eng

KW - essential variable; identification minor; essential arity gap

UR - http://eudml.org/doc/276580

ER -

## References

top- [1] J. Berman and A. Kisielewicz, On the number of operations in a clone, Proc. Amer. Math Soc. 122 (1994), 359-369. doi: 10.1090/S0002-9939-1994-1198450-9 Zbl0821.08002
- [2] Yu. Breitbart, On the essential variables of functions in the algebra of logic, Dokl. Acad. Sci. USSR, (in Russian) 172 vol. 1 (1967), 9-10 .
- [3] K. Chimev, Separable sets of arguments of functions, MTA SzTAKI Tanulmanyok, 180 (1986), 173.
- [4] K. Chimev, On some properties of functions, Colloquia Mathematica Societatis Janos Bolyai, Szeged (1981), 97-110.
- [5] M. Couceiro and E. Lehtonen, On the arity gap of finite functions: results and applications, Int. Conf. on Relations, Orders and Graphs: Interaction with Computer Science, Nouha Editions, Sfax, (2008), pp. 65-72, (http://www.math.tut.fi/algebra/papers/ROGICS08-CL.pdf).
- [6] M. Couceiro and E. Lehtonen, Generalizations of Swierczkowski's lemma and the arity gap of finite functions, Discrete Mathematics, (2009),. doi: 10.1016/j.disc.2009.04.009. Zbl1200.08001
- [7] K. Denecke and J. Koppitz, Essential variables in hypersubstitutions, Algebra Universalis 46 (2001), 443-454. doi: 10.1007/PL00000353 Zbl1058.08004
- [8] D. Kovachev, On a class of discrete functions, Acta Cybernetica, (Szeged) 17 (3) (2006), 513-519. Zbl1100.05011
- [9] O. Lupanov, On a class of schemes of functional elements, Problemi Kybernetiki (in Russian) 9 (1963), 333-335.
- [10] A. Salomaa, On essential variables of functions, especially in the algebra of logic, Annales Academia Scientiarum Fennicae, Ser. A 333 (1963), 1-11. Zbl0134.00703
- [11] Sl. Shtrakov and K. Denecke, Essential variables and separable sets in universal algebra, Taylor & Francis, Multiple-Valued Logic 8 (2) (2002), 165-182. Zbl1022.08002
- [12] Sl. Shtrakov, Essential variables and positions in terms, Algebra Universalis 61 (3-4) (2009), 381-397. doi: 10.1007/s00012-009-0023-1 Zbl1197.08003
- [13] Sl. Shtrakov, Tree automata and essential input variables, Contributions to General Algebra, Verlag Johannes Heyn, Klagenfurt 13 (2001), 309-320. Zbl0986.68071
- [14] Sl. Shtrakov, Essential arity gap of Boolean functions, Serdica Journal of Computing 2 (3) (2008), 249-266. Zbl1170.06005
- [15] R. Willard, Essential arities of term operations in finite algebras, Discrete Mathematics 149 (1996), 239-259. doi: 10.1016/0012-365X(94)00323-B Zbl0840.08005