Efficient Parallel Evaluation of Straight-Line Code and Arithmetic Circuits

DOI10.1137/0217044zbMath0651.68044OpenAlexW2048972466MaRDI QIDQ3796739

Erich L. Kaltofen, Vijaya Ramachandran, Gary Lee Miller

Publication date: 1988

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

Full work available at URL: https://doi.org/10.1137/0217044

zbMATH Keywords

parallel algorithmarithmetic circuitsstraight-line programstraight-line code

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30) Applications of graph theory to circuits and networks (94C15)

Related Items

Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, An optimal EREW PRAM algorithm for minimum spanning tree verification, How hard is to compute the edit distance, Boolean circuits versus arithmetic circuits, Parallel construction of binary trees with near optimal weighted path length, Parallel evaluation of arithmetic circuits, The complexity of two problems on arithmetic circuits, Non-commutative arithmetic circuits: depth reduction and size lower bounds, How hard is computing the edit distance?, Size-depth trade-offs for monotone arithmetic circuits, The complexity of computing maximal word functions