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.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.