KIAM Main page Web Library  •  Publication Searh  Русский 
Publication

Article collection "Mathematical Problems of Cybernetics" №2, Moscow, 1989
Authors: Karpova N.A.
On limited memory computations
Abstract:
Let the logic gates (corresponding to Boolean functions) in a circuit be numbered according to their order of functioning. We introduce the requirement for the output value of a gate (either 0 or 1) to be stored in a register, i.e. a memory element, until all the gates that use this output value have performed their computations. We investigate the Shannon function under the condition that no more than t memory elements are used. We use a set of gates consisting of all p-variable Boolean functions. For t=1 circuits realizing an arbitrary Boolean function may be constructed only if p grows alongside with n. In this case we establish the order of growth of the Shannon function. For a certain range of values of p the Shannon function order of growth is established for t=2. For all fixed t ≥ 3 and p ≥ 2 we establish the asymptotic value of the Shannon function.
Keywords:
circuit, register, Shannon function
Publication language: russian,  pages: 14 (p. 131-144)
Research direction:
Mathematical problems and theory of numerical methods
Russian source text:
List of publications citation:
Export link to publication in format:   RIS    BibTeX
About authors:
  • Karpova Nataliya Aleksandrovna,  KIAM RAS