Parallel random access machines with bounded memory wordsize

DOI10.1016/0890-5401(91)90069-EzbMath0723.68041MaRDI QIDQ757038

Stephen J. Bellantoni

Publication date: 1991

Published in: Information and Computation (Search for Journal in Brave)

zbMATH Keywords

parallel computationincomparabilityparallel random access machinesboolean circuitshierarchy of machine classesinfinitely many memory cellswordsize

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Simulation of PRAMs with scan primitives by unbounded fan-in circuits ⋮ PRAMs with variable word-size

Cites Work

• Parallel computation and conflicts in memory access
• Simulation of Parallel Random Access Machines by Circuits
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• On Parallel Searching
• A fast parallel algorithm for routing in permutation networks

This page was built for publication: Parallel random access machines with bounded memory wordsize