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

Abstract

top
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.

How to cite

top

Slavcho 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. [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. [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. [3] K. Chimev, Separable sets of arguments of functions, MTA SzTAKI Tanulmanyok, 180 (1986), 173. 
  4. [4] K. Chimev, On some properties of functions, Colloquia Mathematica Societatis Janos Bolyai, Szeged (1981), 97-110. 
  5. [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. [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. [7] K. Denecke and J. Koppitz, Essential variables in hypersubstitutions, Algebra Universalis 46 (2001), 443-454. doi: 10.1007/PL00000353 Zbl1058.08004
  8. [8] D. Kovachev, On a class of discrete functions, Acta Cybernetica, (Szeged) 17 (3) (2006), 513-519. Zbl1100.05011
  9. [9] O. Lupanov, On a class of schemes of functional elements, Problemi Kybernetiki (in Russian) 9 (1963), 333-335. 
  10. [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. [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. [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. [13] Sl. Shtrakov, Tree automata and essential input variables, Contributions to General Algebra, Verlag Johannes Heyn, Klagenfurt 13 (2001), 309-320. Zbl0986.68071
  14. [14] Sl. Shtrakov, Essential arity gap of Boolean functions, Serdica Journal of Computing 2 (3) (2008), 249-266. Zbl1170.06005
  15. [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

NotesEmbed ?

top

You must be logged in to post comments.