Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
DOI10.1016/0304-3975(89)90116-3zbMath0678.68032OpenAlexW2014403984MaRDI QIDQ1124332
Michael A. Palis, Jik H. Chang, Oscar H. Ibarra
Publication date: 1989
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(89)90116-3
triangular arraysinterconnected networkscomplexity of languagesarrays of finite-state machinesk-dimensional mesh-connected arraysspace-bounded TMtime-bounded ATMtree arrays
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (3)
Cites Work
- Unnamed Item
- Iterative tree automata
- Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
- On iterative and cellular tree arrays
- Tree-size bounded alternation
- On uniform circuit complexity
- Iterative arrays with direct central control
- A Generalized Dictionary Machine for VLSI
- Parallel Parsing Algorithms and VLSI Implementations for Syntactic Pattern Recognition
- Simulation of Parallel Random Access Machines by Circuits
- Sequential Machine Characterizations of Trellis and Cellular Automata and Applications
- Iterative tree arrays with logarithmic depth†
- Triangle cellular automata
- Alternation
- A universal interconnection pattern for parallel computers
- Speed of Recognition of Context-Free Languages by Array Automata
- On Some Open Problems in the Theory of Cellular Automata
- Real-Time Computation by n-Dimensional Iterative Arrays of Finite-State Machines
This page was built for publication: Efficient simulations of simple models of parallel computation by time- bounded ATMs and space-bounded TMs
