Time Bounded Random Access Machines with Parallel Processing
From MaRDI portal
Publication:4181956
DOI10.1145/322108.322119zbMath0398.68014OpenAlexW2081608347MaRDI QIDQ4181956
Michael J. Stimson, Walter J. Savitch
Publication date: 1979
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/322108.322119
Parallel ProcessingComplexity Of Parallel AlgorithmsEquivalence Of Nondeterministic Polynomial TimeTime Bounded Random Access MachinesUniform Cost Criterion
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of operating systems (68N25)
Related Items
Array processing machines: an abstract model ⋮ On nondeterminism in parallel computation ⋮ The problem of space invariance for sequential machines ⋮ Parallel consistent labeling algorithms ⋮ Squeezing Feasibility ⋮ Complexity theory of parallel time and hardware ⋮ On uniform circuit complexity ⋮ Division in idealized unit cost RAMs ⋮ Number of quantifiers is better than number of tape cells ⋮ Nearly Work-Efficient Parallel Algorithm for Digraph Reachability ⋮ Unnamed Item ⋮ Hierarchies of recursive computations† ⋮ Fuzzy context-free languages. II: Recognition and parsing algorithms ⋮ Parallel random access machines with powerful instruction sets
