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.
@article{bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1171,
author = {Slavcho Shtrakov and J\"org Koppitz},
title = {On finite functions with non-trivial arity gap},
journal = {Discussiones Mathematicae - General Algebra and Applications},
volume = {30},
year = {2010},
pages = {217-245},
zbl = {1245.08004},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1171}
}
Slavcho Shtrakov; Jörg Koppitz. On finite functions with non-trivial arity gap. Discussiones Mathematicae - General Algebra and Applications, Tome 30 (2010) pp. 217-245. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1171/
[000] [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 | Zbl 0821.08002
[001] [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 .
[002] [3] K. Chimev, Separable sets of arguments of functions, MTA SzTAKI Tanulmanyok, 180 (1986), 173.
[003] [4] K. Chimev, On some properties of functions, Colloquia Mathematica Societatis Janos Bolyai, Szeged (1981), 97-110.
[004] [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).
[005] [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. | Zbl 1200.08001
[006] [7] K. Denecke and J. Koppitz, Essential variables in hypersubstitutions, Algebra Universalis 46 (2001), 443-454. doi: 10.1007/PL00000353 | Zbl 1058.08004
[007] [8] D. Kovachev, On a class of discrete functions, Acta Cybernetica, (Szeged) 17 (3) (2006), 513-519. | Zbl 1100.05011
[008] [9] O. Lupanov, On a class of schemes of functional elements, Problemi Kybernetiki (in Russian) 9 (1963), 333-335.
[009] [10] A. Salomaa, On essential variables of functions, especially in the algebra of logic, Annales Academia Scientiarum Fennicae, Ser. A 333 (1963), 1-11. | Zbl 0134.00703
[010] [11] Sl. Shtrakov and K. Denecke, Essential variables and separable sets in universal algebra, Taylor & Francis, Multiple-Valued Logic 8 (2) (2002), 165-182. | Zbl 1022.08002
[011] [12] Sl. Shtrakov, Essential variables and positions in terms, Algebra Universalis 61 (3-4) (2009), 381-397. doi: 10.1007/s00012-009-0023-1 | Zbl 1197.08003
[012] [13] Sl. Shtrakov, Tree automata and essential input variables, Contributions to General Algebra, Verlag Johannes Heyn, Klagenfurt 13 (2001), 309-320. | Zbl 0986.68071
[013] [14] Sl. Shtrakov, Essential arity gap of Boolean functions, Serdica Journal of Computing 2 (3) (2008), 249-266. | Zbl 1170.06005
[014] [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 | Zbl 0840.08005