Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
1985 | 10.1016/0022-0000(85)90015-7 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
polynomial size circuit,n-bit number,size o,unbounded fan-in circuit,nontrivial group,semigroup product iff,finite semigroups,primitive recursive function,associative function,constant depth,n element,semigroup product | Discrete mathematics,Combinatorics,Bicyclic semigroup,Associative property,Primitive recursive function,Cancellative semigroup,Polynomial,Prefix,Semigroup,Mathematics,Computation | Journal |
Volume | Issue | ISSN |
30 | 2 | Journal of Computer and System Sciences |
ISBN | Citations | PageRank |
0-89791-099-0 | 57 | 5.44 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Ashok K. Chandra | 1 | 3116 | 1215.02 |
| Steven Fortune | 2 | 57 | 5.44 |
| Richard J. Lipton | 3 | 6412 | 1796.57 |