PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2010 | 30 | 2 | 217-245
Tytuł artykułu

On finite functions with non-trivial arity gap

Treść / Zawartość
Warianty tytułu
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.
Twórcy
  • Department of Computer Science, South-West University, 2700 Blagoevgrad, Bulgaria
  • 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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgaa_1171
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.