Simulation of Parallel Random Access Machines by Circuits

DOI10.1137/0213027zbMATH Open0533.68048OpenAlexW1967575173MaRDI QIDQ3316595FDOQ3316595

Authors: Uzi Vishkin, Larry J. Stockmeyer

Publication date: 1984

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

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

Recommendations

Parallelism in random access machines
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
Limits on the power of concurrent-write parallel machines
Parallel random access machines with bounded memory wordsize

complexity measures computational power circuit complexity combinational circuits alternating Turing machines parallel RAM parallel time complexity synchronous parallelism

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Cited In (66)

Title not available (Why is that?)
Advocating ownership
Imperative process algebra and models of parallel computation
Faster all-pairs shortest paths via circuit complexity
Collapsing the hierarchy of parallel computational models
Thresholds for extreme orientability
Computation models and function algebras
On the power of families of recognizer spiking neural P systems
From circuit complexity to faster all-pairs shortest paths
Parallelizing time with polynomial circuits
Arithmetizing uniform $NC$
Extensions of an idea of McNaughton
Parallel complexity of algebraic operations
Lower bounds for recognizing small cliques on CRCW PRAM's
Two $P$-complete problems in the theory of the reals
An NC algorithm for recognizing tree adjoining languages
The complexity of ranking simple languages
Algorithmic analysis of priority-based bin packing
Lower bound arguments with ``inaccessible numbers
Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
Lowerbounds for Bisimulation by Partition Refinement
Multiplication, division, and shift instructions in parallel random access machines
Parallel pointer machines
Simulation of PRAMs with scan primitives by unbounded fan-in circuits
Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs
Time lower bounds do not exist for CRCW PRAMs
Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
An optimal parallel connectivity algorithm
Parallel complexity of logical query programs
Parallel random access machines with bounded memory wordsize
A parallelizable lexicographically first maximal edge-induced subgraph problem
The parallel complexity of two problems on concurrency
Parallel computation with threshold functions
Restricted CRCW PRAMs
Properties that characterize LOGCFL
Graph layout problems
A parallel-design distributed-implementation (PDDI) general-purpose computer
The complexity of short two-person games
Feasible real random access machines
On uniformity within $NC^ 1$
Parallel computation for well-endowed rings and space-bounded probabilistic machines
Array processing machines: an abstract model
Faster optimal parallel prefix sums and list ranking
On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs
The size and depth of layered Boolean circuits
The bulk-synchronous parallel random access machine
Efficient simulation of circuits by EREW PRAMs
Subtree isomorphism is in random NC
Learning in parallel
On similarity and duality of computation (I)
Unambiguity of circuits
Parallel models of computation: An introductory survey
Tight complexity bounds for term matching problems
Limits on the power of concurrent-write parallel machines
Subtree isomorphism is NC reducible to bipartite perfect matching
Modular exponentiation via the explicit Chinese remainder theorem
Title not available (Why is that?)
Large parallel machines can be extremely slow for small problems
Separating NC along the $\delta$ axis
The invariant problem for binary string structures and the parallel complexity theory of queries
A query language for NC
Title not available (Why is that?)
Data independence of read, write, and control structures in PRAM computations
On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
Using maximal independent sets to solve problems in parallel
Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

This page was built for publication: Simulation of Parallel Random Access Machines by Circuits

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