Time Bounded Random Access Machines with Parallel Processing

DOI10.1145/322108.322119MaRDI QIDQ4181956zbMATH OpenOpenAlexFDO

Authors Walter Savitch, Michael J. Stimson

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

Complexity Of Parallel AlgorithmsEquivalence Of Nondeterministic Polynomial TimeParallel ProcessingTime Bounded Random Access MachinesUniform Cost Criterion

Mathematics Subject Classification ID

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

Cited in

(17)

• Array processing machines: an abstract model
• On nondeterminism in parallel computation
• The problem of space invariance for sequential machines
• Parallel consistent labeling algorithms
• 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
• Fuzzy context-free languages. II: Recognition and parsing algorithms
• Squeezing Feasibility
• Hierarchies of recursive computations†
• Parallel random access machines with powerful instruction sets
• scientific article; zbMATH DE number 7561283 (Why is no real title available?)
• Nearly work-efficient parallel algorithm for digraph reachability
• Parallel machine models: how they are and where are they going
• Artificial intelligence and inherent mathematical difficulty
• Towards a complexity theory of synchronous parallel computation

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4181956)