RUS  ENG
Full version
JOURNALS // Diskretnaya Matematika // Archive

Diskr. Mat., 1990 Volume 2, Issue 4, Pages 60–62 (Mi dm884)

A lower bound on the register complexity of the computation of terms

Yu. V. Yatsishin


Abstract: 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$.

UDC: 510.6

Received: 13.06.1989



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2026