The parallel evaluation of arithmetic expressions involving one-variable functions

This paper presents an algorithm for restructuring arithmetic expressions involving one-variable functions for parallel computations. The paper gives upper bounds for the restructuring time of a given expression on a serial processor and for the time for its parallel computation as well as for the number of required processors.
The restructuring of arithmetic expression involving one-variable functions is reduced to the restructuring arithmetic expressions, which is called in the present paper the incomplete arithmetic expressions. From viewpoint of computing expressions problem this expression is a generalization of arithmetic expression. They involve ordinary variables and variables the value of which must be computed by some algorithm simultaneusly with expression. The paper presents algorithms for restructuring incomplete arithmetic expressions for parallel computing which is a generalization of the known algorithm of Muller D. E. and Preparata F. P.