Time Bounded Random Access Machines with Parallel Processing

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

zbMATH Keywords

Parallel ProcessingComplexity Of Parallel AlgorithmsEquivalence Of Nondeterministic Polynomial TimeTime Bounded Random Access MachinesUniform Cost Criterion

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Theory of operating systems (68N25)

Related Items (14)

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

This page was built for publication: Time Bounded Random Access Machines with Parallel Processing