The Parallel Evaluation of General Arithmetic Expressions
From MaRDI portal
Publication:4401551
DOI10.1145/321812.321815zbMath0276.68010OpenAlexW2130566259WikidataQ56813864 ScholiaQ56813864MaRDI QIDQ4401551
Publication date: 1974
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/321812.321815
Analysis of algorithms and problem complexity (68Q25) General topics in the theory of software (68N01)
Related Items
Improved parallel solution of a triangular linear system, Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity, A chained-matrices approach for parallel computation of continued fractions and its applications, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, On computing accurate singular values and eigenvalues of matrices with acyclic graphs, Finding least-weight subsequences with fewer processors, A Generalization of Spira’s Theorem and Circuits with Small Segregators or Separators, Finding small simple cycle separators for 2-connected planar graphs, An optimal parallel algorithm using exclusive read/writes for the rectilinear Voronoi diagram, The delay of circuits whose inputs have specified arrival times, Optimal edge ranking of trees in polynomial time, Dynamic expression trees, Optimal computation of prefix sums on a binary tree of processors, Finding all periods and initial palindromes of a string in parallel, Fast parallel graph searching with applications, Optimal parallel construction of prescribed tournaments, Communication-efficient parallel algorithms for distributed random-access machines, Types of depth and formula size, A parallel bucket sort, An optimally efficient selection algorithm, A generalization of Spira's theorem and circuits with small segregators or separators, Sweep methods for parallel computational geometry, Parallel computation of polynomial GCD and some related parallel computations over abstract fields, Constructing small tree grammars and small circuits for formulas, Feasible arithmetic computations: Valiant's hypothesis, Parallel computational geometry, Parallel local search, A note on parallel algorithms for optimal h-v drawings of binary trees, Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications., Balancing bounded treewidth circuits, Size-depth tradeoff in non-monotone Boolean formulae, Algebraic geometry and representation theory in the study of matrix multiplication complexity and other problems in theoretical computer science, A space efficient algorithm for the monotone planar circuit value problem, Two parallel algorithms for finding all minimal maximum subsequences, Scalability and communication in parallel low-complexity lossless compression, Parameterized random complexity, Toward Better Formula Lower Bounds: The Composition of a Function and a Universal Relation, Methods and means of parallel processing of information, On the applicability of Post's lattice, On treewidth, separators and Yao's garbling, Sufficient conditions for the existence of spanning colored trees in edge-colored graphs, Parallel tree pattern matching, A complexity theory of efficient parallel algorithms, An optimal parallel algorithm for linear programming in the plane, Parallel recognition of complement reducible graphs and cotree construction, Subtree isomorphism is in random NC, Optimal computation of shortest paths on doubly convex bipartite graphs, Use of algebraically independent numbers for zero recognition of polynomial terms., A unified approach to parallel depth-first traversals of general trees, Processor-efficient implementation of a maximum flow algorithm, Planar orientations with low out-degree and compaction of adjacency matrices, Inapproximability and polynomial-time approximation algorithm for UET tasks on structured processor networks, Data-movement-intensive problems: Two folk theorems in parallel computation revisited, Parallel restructuring and evaluation of expressions, Optimal parallel algorithms for forest and term matching, A work-time optimal algorithm for computing all string covers, Parallel detection of all palindromes in a string, Fast parallel string prefix-matching, Parallel rectilinear shortest paths with rectangular obstacles, Parallel solution of Toeplitzlike linear systems, Engineering parallel string sorting, A parallel space saving algorithm for frequent items and the Hurwitz zeta distribution, Symbolic computation of derivations using labelled trees, Towards optimal simulations of formulas by bounded-width programs, Parallel recognition of series-parallel graphs, Counting paths in VPA is complete for \(\#\mathrm{NC}^1\), A faster parallel algorithm for a matrix searching problem, Scheduling \(UET\)-tasks on a star network: complexity and approximation, Bounds on the parallel evaluation of arithmetic expressions using associativity and commutativity, On measures of space over real and complex numbers, The time required to evaluate division-free arithmetic expressions, The cache complexity of multithreaded cache oblivious algorithms, Constructing arrangements optimally in parallel, On limits on the computational power of data-accumulating algorithms, Parallel computation of the Burrows Wheeler transform in compact space, Building heaps in parallel, Optimal parallel quicksort on EREW PRAM, Algebraic Complexity Classes, Optimal algorithms for the single and multiple vertex updating problems of a minimum spanning tree, Optimal circular arc representations: Properties, recognition, and construction, Approximate parallel scheduling. II: Applications to logarithmic-time optimal parallel graph algorithms, $$P\mathop{ =}\limits^{?}NP$$, Computing Prüfer codes efficiently in parallel, Circuits over PP and PL, An \(O(n \log n)\) time algorithm for computing the path-length distance between trees, Lower bounds on the depth of monotone arithmetic computations, Improved parallel construction of wavelet trees and rank/select structures, An algorithm for the Tutte polynomials of graphs of bounded treewidth, On the rapid computation of various polylogarithmic constants, OPTIMAL BUCKET SORTING AND OVERLAP REPRESENTATIONS, An optimal parallel connectivity algorithm, Geometric complexity theory: an introduction for geometers, Size-depth trade-offs for monotone arithmetic circuits, On parallel rectilinear obstacle-avoiding paths, On optimal parallel computations for sequences of brackets, Parallel solutions to geometric problems in the scan model of computation, Testing string superprimitivity in parallel, Size-depth tradeoffs for Boolean formulae, Resequencing a set of strings based on a target string, Limitations of sums of bounded read formulas and ABPs, Context-based compression of binary images in parallel, Grammar-Based Tree Compression, Sequential and parallel algorithms for embedding problems on classes of partial k-trees, Lower bounds to processor-time tradeoffs under bounded-speed message propagation, SPEEDUP-AWARE CO-SCHEDULES FOR EFFICIENT WORKLOAD MANAGEMENT, Computing the all-pairs longest chains in the plane, Parallel construction of quadtrees and quality triangulations, AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗, THE MAXIMUM WEIGHT PERFECT MATCHING PROBLEM FOR COMPLETE WEIGHTED GRAPHS IS IN PC∗†, On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?, An nc algorithm to recognize hhd-free graphs, Characterizing Propositional Proofs as Noncommutative Formulas, On a relation between the depth and complexity of monotone Boolean formulas, The parallel complexity of tree embedding problems (extended abstract), Shadows of Newton polytopes, Malleable scheduling beyond identical machines, An improved approximation algorithm for scheduling monotonic moldable tasks, Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms, Unnamed Item, Equations for secant varieties of Chow varieties, NC algorithms for antidirected hamiltonian paths and cycles in tournaments, (Time × space)-efficient implementations of hlerarchical conceptual models, Распараллеливание численного алгоритма решения задачи Коши для нелинейного дифференциального уравнения дробного переменного порядка с помощью технологии OpenMP, Parallel algorithms for solving linear equations using givens transformations, Oracle-guided scheduling for controlling granularity in implicitly parallel languages, Efficient string matching on packed texts, Nearly Work-Efficient Parallel Algorithm for Digraph Reachability, A Quadratic Size-Hierarchy Theorem for Small-Depth Multilinear Formulas, The method of shifted partial derivatives cannot separate the permanent from the determinant, Small-Depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication with Applications, Two-variable linear programming in parallel, Trade-offs between communication throughput and parallel time, Lower Bounds for Syntactically Multilinear Algebraic Branching Programs, A faster parallel algorithm for a matrix searching problem, PARALLEL CONSTRUCTION OF QUADTREES AND QUALITY TRIANGULATIONS, Optimal parallel algorithms for periods, palindromes and squares, Unnamed Item, Fast Sequential and Parallel Vertex Relabelings of Km,m, Short Proofs for the Determinant Identities, Optimal Parallel Searching an Array for Certain Repetitions, Improved parallel algorithms for finding the most vital edge of a graph with respect to minimum spanning tree∗, Restructuring Expression Dags for Efficient Parallelization, ON THE POWER OF SOME PRAM MODELS, An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction, Space-Efficient Parallel Construction of Succinct Representations of Suffix Tree Topologies
