Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
The computation of finite semigroups using unbounded fan-in circuits are considered. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f circuits of size O(nf-1(n)) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers. © 1985.
Ehud Altman, Kenneth R. Brown, et al.
PRX Quantum
John R. Kender, Rick Kjeldsen
IEEE Transactions on Pattern Analysis and Machine Intelligence
W.F. Cody, H.M. Gladney, et al.
SPIE Medical Imaging 1994
Matthew A Grayson
Journal of Complexity