Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size
Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size
The prefix problem consits of computing all the products $x_{0}x_{1}\cdots x_{j}(j = 0,\cdots, N-1)$, given a sequence ${\bf x} = (x_{0}, x_{1},\cdots , x_{N-1})$ of elements in a semigroup. It is shown that there are unbounded fan-in and fan-out Boolean circuits for the prefix problem with constant depth and linear …