Geodesic
Lower bounds for the complexity of systems of vectors of $k$-valued logic
Diskretnaya Matematika, Tome 10 (1998) no. 1, pp. 46-62 
A. V. Chashkin. Lower bounds for the complexity of systems of vectors of $k$-valued logic. Diskretnaya Matematika, Tome 10 (1998) no. 1, pp. 46-62. http://geodesic.mathdoc.fr/item/DM_1998_10_1_a4/
@article{DM_1998_10_1_a4,
     author = {A. V. Chashkin},
     title = {Lower bounds for the complexity of systems of vectors of $k$-valued logic},
     journal = {Diskretnaya Matematika},
     pages = {46--62},
     year = {1998},
     volume = {10},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1998_10_1_a4/}
}
TY  - JOUR
AU  - A. V. Chashkin
TI  - Lower bounds for the complexity of systems of vectors of $k$-valued logic
JO  - Diskretnaya Matematika
PY  - 1998
SP  - 46
EP  - 62
VL  - 10
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/DM_1998_10_1_a4/
LA  - ru
ID  - DM_1998_10_1_a4
ER  - 
%0 Journal Article
%A A. V. Chashkin
%T Lower bounds for the complexity of systems of vectors of $k$-valued logic
%J Diskretnaya Matematika
%D 1998
%P 46-62
%V 10
%N 1
%U http://geodesic.mathdoc.fr/item/DM_1998_10_1_a4/
%G ru
%F DM_1998_10_1_a4

Voir la notice de l'article provenant de la source Math-Net.Ru

Exact values of the complexity of generating narrow vector systems of $k$-valued logic by circuits over various bases are found. It is shown that lower bounds for the complexity of generating narrow vector systems that are asymptotically greater than the bounds obtained in this work imply exponential lower bounds for the complexity of functions of $k$-valued logic when they are realized by circuits over complete bases.This research was supported by the Russian Foundation for Basic Research, grant 96–01–01068.