Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size

DOI10.1137/0219016zbMath0695.68019OpenAlexW2050955923MaRDI QIDQ3471696

Gianfranco Bilardi, Franco P. Preparata

Publication date: 1990

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/6751

zbMATH Keywords

semigroupsBoolean circuitssuperconcentratorssize-depth trade-offprefix problem

Mathematics Subject Classification ID

Circuits, networks (94C99) Theory of operating systems (68N25) Algorithms in computer science (68W99) Semigroups (20M99)

Related Items (3)

The average case complexity of the parallel prefix problem ⋮ Circuit complexity of regular languages ⋮ WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY

This page was built for publication: Characterization of Associative Operations with Prefix Circuits of Constant Depth and Linear Size