On nondeterminism in parallel computation

DOI10.1016/0304-3975(86)90139-8zbMath0638.68032OpenAlexW2001761554MaRDI QIDQ1099612

Patrick W. Dymond

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90139-8

zbMATH Keywords

hardware modification machineNondeterministic parallel complexity classes

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items

Parallel pointer machines, Nondeterministics circuits, space complexity and quasigroups, Speedups of deterministic machines by synchronous parallel machines

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Speedups of deterministic machines by synchronous parallel machines
• On uniform circuit complexity
• Towards a complexity theory of synchronous parallel computation
• On tape-bounded complexity classes and multihead finite automata
• A characterization of the power of vector machines
• Storage Modification Machines
• Alternation
• A universal interconnection pattern for parallel computers
• Parallel random access machines with powerful instruction sets
• On Relating Time and Space to Size and Depth
• Time Bounded Random Access Machines with Parallel Processing
• On the n^{log n} isomorphism technique (A Preliminary Report)
• Parallelism in random access machines
• Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines