Speedup of determinism by alternation for multidimensional Turing machines

DOI10.1016/0304-3975(94)90247-XzbMath0938.68650MaRDI QIDQ1341727

Louis Mak

Publication date: 27 June 2000

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

Mathematics Subject Classification ID

Cites Work

• Speedups of deterministic machines by synchronous parallel machines
• Parallel computation with threshold functions
• On alternation. II. A graph theoretic approach to determinism versus nondeterminism
• Simulations among multidimensional Turing machines
• Rounds versus time for the two person pebble game
• A New Pebble Game that Characterizes Parallel Complexity Classes
• Alternation
• An Optimal Parallel Algorithm for Formula Evaluation
• Relations Among Complexity Measures
• Boolean Memories
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item