Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size
Gianfranco Bilardi, F. P. Preparata · SIAM Journal on Computing · 1990
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 size if and only if the Cayley graph of the semigroup does not contain a special type of cycle called monoidal cycle.