Unbounded fan-in circuits and associative functions
type: Item
instance of: scholarly article
title: Unbounded fan-in circuits and associative functions
zbMATH Open document ID: 0604.68051
DOI: 10.1016/0022-0000(85)90015-7
author: Ashok K. Chandra
author: Steven Fortune
author: Richard J. Lipton
published in: Journal of Computer and System Sciences
publication date: 1985-01-01T00:00:00Z
review text: The computation of finite semigroups using unbounded fan-in circuits is 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 20M35
Mathematics Subject Classification ID: 94C10
Mathematics Subject Classification ID: 68Q70
Mathematics Subject Classification ID: 68Q45
zbMATH DE Number: 3976337
zbMATH Keywords: parallel computation
zbMATH Keywords: circuit complexity
zbMATH Keywords: computation of finite semigroups
zbMATH Keywords: semigroup product
zbMATH Keywords: primitive recursive function
MaRDI profile type: Publication
full work available at URL: 0022-0000(85)90015-7
OpenAlex ID: W2031713274
cites work: Q3321475
cites work: Parity, circuits, and the polynomial-time hierarchy
cites work: Parallel Prefix Computation
cites work: Q5641083
cites work: Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: Q4074359
cites work: Implementation of simultaneous memory address access in models that forbid it
cites work: A unified approach to models of synchronous parallel machines
description: scientific article; zbMATH DE number 3976337