Geodesic
A~lower bound on the register complexity of the computation of terms
Diskretnaya Matematika, Tome 2 (1990) no. 4, pp. 60-62

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

We consider a problem of calculating the terms $t$ of a family $T$ using a computer according to a program $\Pi (t)$. The quantity $S(t)=\min|\Pi (t)|$ is called the register complexity of calculating the term $t$, where $|\Pi (t)|$ is the number of registers used by the program $\Pi (t)$. We prove that $S(t)\geqslant h/2+1$ for the family of terms of height $h$. 
@article{DM_1990_2_4_a5,
     author = {Yu. V. Yatsishin},
     title = {A~lower bound on the register complexity of the computation of terms},
     journal = {Diskretnaya Matematika},
     pages = {60--62},
     publisher = {mathdoc},
     volume = {2},
     number = {4},
     year = {1990},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DM_1990_2_4_a5/}
}
TY  - JOUR
AU  - Yu. V. Yatsishin
TI  - A~lower bound on the register complexity of the computation of terms
JO  - Diskretnaya Matematika
PY  - 1990
SP  - 60
EP  - 62
VL  - 2
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DM_1990_2_4_a5/
LA  - ru
ID  - DM_1990_2_4_a5
ER  - 
%0 Journal Article
%A Yu. V. Yatsishin
%T A~lower bound on the register complexity of the computation of terms
%J Diskretnaya Matematika
%D 1990
%P 60-62
%V 2
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DM_1990_2_4_a5/
%G ru
%F DM_1990_2_4_a5
Yu. V. Yatsishin. A~lower bound on the register complexity of the computation of terms. Diskretnaya Matematika, Tome 2 (1990) no. 4, pp. 60-62. http://geodesic.mathdoc.fr/item/DM_1990_2_4_a5/