On finite functions with non-trivial arity gap

• Autorzy: Slavcho Shtrakov , Jörg Koppitz
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

essential variable; identification minor; essential arity gap

Kategorie tematyczne

• 03G25: Other algebras related to logic
• 05E05: Symmetric functions and generalizations

• Wydawca: Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Góra
• Czasopismo: Discussiones Mathematicae - General Algebra and Applications
• Rocznik: 2010
• Tom: 30
• Numer: 2
• Strony: 217-245

Daty

wydano

2010

otrzymano

2009-12-15

poprawiono

2010-01-14

Twórcy

autor

Slavcho Shtrakov

• Department of Computer Science, South-West University, 2700 Blagoevgrad, Bulgaria

autor

Jörg Koppitz

• Institute of Mathematics, University of Potsdam, 14415 Potsdam, Germany

Bibliografia

• [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
• [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.
• [7] K. Denecke and J. Koppitz, Essential variables in hypersubstitutions, Algebra Universalis 46 (2001), 443-454. doi: 10.1007/PL00000353
• [8] D. Kovachev, On a class of discrete functions, Acta Cybernetica, (Szeged) 17 (3) (2006), 513-519.
• [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.
• [11] Sl. Shtrakov and K. Denecke, Essential variables and separable sets in universal algebra, Taylor & Francis, Multiple-Valued Logic 8 (2) (2002), 165-182.
• [12] Sl. Shtrakov, Essential variables and positions in terms, Algebra Universalis 61 (3-4) (2009), 381-397. doi: 10.1007/s00012-009-0023-1
• [13] Sl. Shtrakov, Tree automata and essential input variables, Contributions to General Algebra, Verlag Johannes Heyn, Klagenfurt 13 (2001), 309-320.
• [14] Sl. Shtrakov, Essential arity gap of Boolean functions, Serdica Journal of Computing 2 (3) (2008), 249-266.
• [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

Identyfikatory

DOI

10.7151/dmgaa.1171