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

Gianfranco Bilardi | Zendy; F. P. Preparata | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

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

Author(s) -

Gianfranco Bilardi,

F. P. Preparata

Publication year - 1990

Publication title -

siam journal on computing

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 1.533

H-Index - 122

eISSN - 1095-7111

pISSN - 0097-5397

DOI - 10.1137/0219016

Subject(s) - prefix , semigroup , mathematics , constant (computer programming) , characterization (materials science) , discrete mathematics , combinatorics , cayley graph , graph , sequence (biology) , bicyclic semigroup , boolean function , computer science , philosophy , linguistics , materials science , biology , genetics , programming language , nanotechnology

The prefix problem consists of computing all the products $x_{0}x_{1} \ldots x_{j} (j = 0, \ldots,N 1)$, given a sequence $x =(x_{0},x_{1},\ldots, 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research