Simulation of Parallel Random Access Machines by Circuits
From MaRDI portal
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
Cited in
(69)- On ranking 1-way finitely ambiguous NL languages and $\# P_1$-complete census functions
- Arithmetizing uniform NC
- Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
- Lower bounds for recognizing small cliques on CRCW PRAM's
- Extensions of an idea of McNaughton
- Two \(P\)-complete problems in the theory of the reals
- An NC algorithm for recognizing tree adjoining languages
- Parallel complexity of algebraic operations
- scientific article; zbMATH DE number 408789 (Why is no real title available?)
- The complexity of ranking simple languages
- Algorithmic analysis of priority-based bin packing
- Advocating ownership
- Lower bound arguments with ``inaccessible numbers
- Randomized and deterministic simulations of PRAMs by parallel machines with restricted granularity of parallel memories
- Imperative process algebra and models of parallel computation
- Evaluating monotone circuits on surfaces
- Faster all-pairs shortest paths via circuit complexity
- Lowerbounds for Bisimulation by Partition Refinement
- Multiplication, division, and shift instructions in parallel random access machines
- Simulation of PRAMs with scan primitives by unbounded fan-in circuits
- Parallel pointer machines
- 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
- Collapsing the hierarchy of parallel computational models
- Parallel complexity of logical query programs
- Thresholds for extreme orientability
- 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
- Computation models and function algebras
- Parallel computation with threshold functions
- On the power of families of recognizer spiking neural P systems
- Properties that characterize LOGCFL
- Restricted CRCW PRAMs
- Graph layout problems
- The complexity of short two-person games
- A parallel-design distributed-implementation (PDDI) general-purpose computer
- On the formalization of the notion of a concurrent algorithm
- Feasible real random access machines
- On uniformity within \(NC^ 1\)
- Array processing machines: an abstract model
- Parallel computation for well-endowed rings and space-bounded probabilistic machines
- 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 bulk-synchronous parallel random access machine
- The size and depth of layered Boolean circuits
- Learning in parallel
- Efficient simulation of circuits by EREW PRAMs
- Subtree isomorphism is in random NC
- 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
- From circuit complexity to faster all-pairs shortest paths
- Modular exponentiation via the explicit Chinese remainder theorem
- Large parallel machines can be extremely slow for small problems
- scientific article; zbMATH DE number 3898252 (Why is no real title available?)
- 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
- Data independence of read, write, and control structures in PRAM computations
- scientific article; zbMATH DE number 3986645 (Why is no real title available?)
- Using maximal independent sets to solve problems in parallel
- An evaluation of massively parallel algorithms for DFA minimization
- Parallelizing time with polynomial circuits
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)
