Simulation of Parallel Random Access Machines by Circuits
From MaRDI portal
Publication:3316595
DOI10.1137/0213027zbMath0533.68048OpenAlexW1967575173MaRDI QIDQ3316595
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
circuit complexitycomplexity measurescomputational powercombinational circuitsalternating Turing machinesparallel RAMparallel time complexitysynchronous parallelism
Related Items
Parallel pointer machines, On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions, Algorithmic analysis of priority-based bin packing, Simulation of PRAMs with scan primitives by unbounded fan-in circuits, Array processing machines: an abstract model, On uniformity within \(NC^ 1\), Limits on the power of concurrent-write parallel machines, Parallel complexity of logical query programs, Faster All-Pairs Shortest Paths via Circuit Complexity, Lower bound arguments with ``inaccessible numbers, Parallel computation with threshold functions, A parallelizable lexicographically first maximal edge-induced subgraph problem, Subtree isomorphism is NC reducible to bipartite perfect matching, Parallel complexity of algebraic operations, A query language for NC, Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs, Extensions of an idea of McNaughton, Graph layout problems, Computation models and function algebras, Lowerbounds for Bisimulation by Partition Refinement, The size and depth of layered Boolean circuits, Parallelizing time with polynomial circuits, Efficient simulation of circuits by EREW PRAMs, Parallel models of computation: An introductory survey, Lower bounds for recognizing small cliques on CRCW PRAM's, Subtree isomorphism is in random NC, The complexity of short two-person games, Properties that characterize LOGCFL, Arithmetizing uniform \(NC\), Data independence of read, write, and control structures in PRAM computations, Learning in parallel, Time lower bounds do not exist for CRCW PRAMs, Using maximal independent sets to solve problems in parallel, The invariant problem for binary string structures and the parallel complexity theory of queries, Multiplication, division, and shift instructions in parallel random access machines, An NC algorithm for recognizing tree adjoining languages, COLLAPSING THE HIERARCHY OF PARALLEL COMPUTATIONAL MODELS, Thresholds for extreme orientability, Tight complexity bounds for term matching problems, Two \(P\)-complete problems in the theory of the reals, Unambiguity of circuits, The complexity of ranking simple languages, Translational lemmas for DLOGTIME-uniform circuits, alternating TMs, and PRAMs, ON THE POWER OF FAMILIES OF RECOGNIZER SPIKING NEURAL P SYSTEMS, On parallel complexity of the subgraph homeomorphism of the subgraph isomorphism problem for classes of planar graphs, Parallel random access machines with bounded memory wordsize, Faster optimal parallel prefix sums and list ranking, Separating NC along the \(\delta\) axis, Modular exponentiation via the explicit Chinese remainder theorem, From Circuit Complexity to Faster All-Pairs Shortest Paths, A parallel-design distributed-implementation (PDDI) general-purpose computer, An optimal parallel connectivity algorithm, Restricted CRCW PRAMs, Large parallel machines can be extremely slow for small problems, The parallel complexity of two problems on concurrency
