Parallel pointer machines

DOI10.1007/BF01200405MaRDI QIDQ2366720zbMATH OpenFDO

Authors Stephen Cook, P. Dymond

Publication date 9 February 1994

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01200405

zbMATH Keywords

alternating machinescomplexity measuresparallel pointer machine

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Cellular automata (computational aspects) (68Q80)

Recommendations

• Hierarchies and space measures for pointer machines
• On time versus space III
• Parallelism in random access machines
• On similarity and duality of computation (I)

Cites work

• A class of algorithms which require nonlinear time to maintain disjoint sets
• A universal interconnection pattern for parallel computers
• Alternation
• Complexity theory of parallel time and hardware
• scientific article; zbMATH DE number 3960999 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 3694633 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 3494307 (Why is no real title available?)
• On nondeterminism in parallel computation
• On Relating Time and Space to Size and Depth
• On similarity and duality of computation (I)
• On uniform circuit complexity
• Parallelism in random access machines
• Simulation of Parallel Random Access Machines by Circuits
• Storage Modification Machines
• Towards a complexity theory of synchronous parallel computation
• Tree-size bounded alternation

Cited in

(14)

• On nondeterminism in parallel computation
• Pointers versus arithmetic in PRAMs
• Data independence of read, write, and control structures in PRAM computations
• Hierarchies and space measures for pointer machines
• Computing with a fixed number of pointers (invited talk)
• scientific article; zbMATH DE number 1823194 (Why is no real title available?)
• scientific article; zbMATH DE number 4108154 (Why is no real title available?)
• scientific article; zbMATH DE number 176163 (Why is no real title available?)
• scientific article; zbMATH DE number 1751214 (Why is no real title available?)
• scientific article; zbMATH DE number 1760142 (Why is no real title available?)
• StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
• The autonomous data language -- concepts, design and formal verification
• Unbounded hardware is equivalent to deterministic Turing machines
• Sequential and parallel algorithms for the NCA problem on pure pointer machines

This page was built for publication: Parallel pointer machines

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