The Parallel Evaluation of Arithmetic Expressions Without Division

DOI10.1109/T-C.1973.223757MaRDI QIDQ5666165zbMATH OpenOpenAlexFDO

Authors Richard P. Brent, David Kuck, Kiyoshi Maruyama

Publication date 1973

Published in IEEE Transactions on Computers (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/t-c.1973.223757

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25)

Cited in

(13)

• On the computational complexity of coalitional resource games
• On a relation between the depth and complexity of monotone Boolean formulas
• The delay of circuits whose inputs have specified arrival times
• Size-depth tradeoff in non-monotone Boolean formulae
• Parallel restructuring and evaluation of expressions
• Some parallel methods for polynomial root-finding
• Lower bounds on the depth of monotone arithmetic computations
• Parameterized random complexity
• Parallelizable algebras
• Bounds on the parallel evaluation of arithmetic expressions using associativity and commutativity
• On the parallel evaluation of division-free arithmetic expressions with fan-in of three
• The time required to evaluate division-free arithmetic expressions
• A quasi-polynomial-time algorithm for sampling words from a context-free language

This page was built for publication: The Parallel Evaluation of Arithmetic Expressions Without Division

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5666165)