Optimal Parallel Generation of a Computation Tree Form

Abstract

Given a general arithmetic expression, we find a computation binary tree representation in O (log n ) time using n /log n processors on a concurrent-read, exclusive-write, parallel random-access machine. A new algorithm is introduced for this purpose. Unlike previous serial and parallel solutions, it is not based on using a stack.