An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
From MaRDI portal
Publication:1108006
DOI10.1016/0020-0190(87)90112-8zbMath0653.68040OpenAlexW2149100697MaRDI QIDQ1108006
Publication date: 1987
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(87)90112-8
NCreversaldeterministic k-tape Turing machineextended parallel computation thesisreduction to sortingshared-memory machinesimultaneous resource boundsuniform circuit
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A parallel-design distributed-implementation (PDDI) general-purpose computer
- Sorting in \(c \log n\) parallel steps
- Some practical simulations of impractical parallel computers
- On uniform circuit complexity
- An Efficient General-Purpose Parallel Computer
- Finding the maximum, merging, and sorting in a parallel computation model
- Ultracomputers
- Parallel permutation and sorting algorithms and a new generalized connection network
- A universal interconnection pattern for parallel computers
- On Relating Time and Space to Size and Depth
- Implementation of simultaneous memory address access in models that forbid it
- Parallelism in random access machines
- On the Number of Stable States in a NOR Network
This page was built for publication: An improved simulation of space and reversal bounded deterministic Turing machines by width and depth bounded uniform circuits
